扫描线
扫描线是一种用于图形上，常被用来解决图形面积、图形周长和二维数点等问题。
扫描线求图形面积
因为图形并不是一个规整的矩形，不方便直接算。很容易就能想到，把这个图形拆成若干个矩形，怎么实现这个过程呢，这时候就需要用到扫描线了。
假设现在有一根线从下往上扫
可以发现若矩形的长出现了变化，就往上扫一下，矩形的宽就是扫过的距离，这样就分成了若干个矩形。
先离散化，再利用差分思想可以通过线段树维护矩形的长。在矩形下边处 \(cnt+1\)，在上边处 \(cnt-1\)，最后 \(cnt\) 有值的区间的长度的和就是矩形的长。需要注意的是，离散化后区间 \(\left[l,l+1\right]\) 其实表示的是原来的区间 \(\left[x_l,x_{l+1}\right)\)。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=1e6+10;
ll x[N<<1],n;
struct node{
ll l,r,h,val;
node(ll _l=0,ll _r=0,ll _h=0,ll _val=0){
l=_l,r=_r,h=_h,val=_val;
}
}seg[N<<1];
bool cmp(node x,node y){
return x.h<y.h;
}
namespace Seg_Tree{
ll ans[N<<3];
int tag[N<<3];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
void push_up(int p,int l,int r){
if(tag[p]){
ans[p]=x[r+1]-x[l];
}
else{
ans[p]=ans[ls(p)]+ans[rs(p)];
}
}
void update(int p,int l,int r,ll q_l,ll q_r,int val){
if(x[r+1]<=q_l||q_r<=x[l]){
return;
}
if(q_l<=x[l]&&x[r+1]<=q_r){
tag[p]+=val;
push_up(p,l,r);
return;
}
int mid=(l+r)>>1;
update(ls(p),l,mid,q_l,q_r,val);
update(rs(p),mid+1,r,q_l,q_r,val);
push_up(p,l,r);
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n);
ll x_1,x_2,y_1,y_2;
for(int i=1;i<=n;i++){
read(x_1),read(y_1),read(x_2),read(y_2);
x[i*2-1]=x_1;x[i*2]=x_2;
seg[i*2-1]=node(x_1,x_2,y_1,1);
seg[i*2]=node(x_1,x_2,y_2,-1);
}
n=n*2;
sort(seg+1,seg+n+1,cmp);
sort(x+1,x+n+1);
int cnt=unique(x+1,x+n+1)-x-1;
ll ans=0;
for(int i=1;i<n;i++){
Seg_Tree::update(1,1,cnt-1,seg[i].l,seg[i].r,seg[i].val);
ans+=Seg_Tree::ans[1]*(seg[i+1].h-seg[i].h);
}
write_endl(ans);
return 0;
}
扫描线求图形周长
咕咕咕
吉司机线段树
吉司机线段树是一种维护区间最值和区间历史最值的线段树。
这道题和【模板】线段树 1 最大的差别是加入了区间取最值和求区间历史最值操作。
先考虑区间取最值操作怎么维护。有个 \(O(n^2)\) 的暴力是一直往下搜，直到 \(l=r\) 或 \(x>\max\limits_{i=l}^r A_i\)，考虑优化它。
吉老师提出了一种方法，维护区间内最大值 maxa 和严格次大值 nxtmax 和最大值的出现次数 cnt，只修改 \(nxtmax\le x \le maxa\) 的区间。
怎么维护呢？考虑用到四个标记 add_a,add_a1,add_b,add_b1，分别表示区间最大值的加标记，区间非最大值的加标记，区间最大值的历史的最大加标记，区间非最大值的历史的最大加标记。
先看更新用的 f 函数怎么做。设 f(p,a,b,c,d) 表示线段树上的点 \(p\) 表示区间的最大值要加 \(a\)，历史最大值要加 \(b\)，非最大值要加 \(c\)，历史非最大值要加 \(d\)。
void f(int p,int a,int b,int c,int d){
tr[p].sum+=a*tr[p].cnt+c*(tr[p].len-tr[p].cnt);
tr[p].maxb=max(tr[p].maxb,tr[p].maxa+b);
tr[p].add_b=max(tr[p].add_b,tr[p].add_a+b);
tr[p].add_b1=max(tr[p].add_b1,tr[p].add_a1+d);
tr[p].add_a+=a;
tr[p].maxa+=a;
tr[p].add_a1+=c;
if(tr[p].nxt_max!=-inf){
tr[p].nxt_max+=c;
}
}
关于直接用当前的加标记更新历史的加标记，感觉非常显然，因为没有下传前，区间最大值和次大值并不会发生改变，所以区间最大值并不会发生改变，所以历史加标记的标记对象仍然维护的是当前区间的最大值/非最大值的历史标记。
再理解一下历史加标记的含义，从上次下传到现在，该区间的最大值/非最大值的加标记。
理解完了 f 函数，push_down,push_up 操作自然就很容易地出来了。
push_down：对于左右区间中的任意一个，若区间最大值等于该区间最大值，就分别用最大值/次大值的加标记更新该区间最大值/次大值，否则均用次大值的加标记更新。
push_up：先判断左右区间最大值是否相同。若相同，将左右区间最大值出现次数相加，并取左右区间的严格次大值中较大的那个作为区间次大值；若不同，取最大值较大的那个区间的最大值及区间次数，并将该区间的严格次大值与另一个区间的最大值比较以更新区间严格次大值。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define int long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=5e5+10,inf=1e18;
int n,a[N],q;
namespace Seg_Tree{
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
struct node{
int add_a,add_b,add_a1,add_b1,maxa,maxb,sum,cnt,len,nxt_max;
}tr[N<<3];
void push_up(int p){
tr[p].maxa=max(tr[ls(p)].maxa,tr[rs(p)].maxa);
tr[p].maxb=max(tr[ls(p)].maxb,tr[rs(p)].maxb);
tr[p].sum=tr[ls(p)].sum+tr[rs(p)].sum;
if(tr[ls(p)].maxa==tr[rs(p)].maxa){
tr[p].nxt_max=max(tr[ls(p)].nxt_max,tr[rs(p)].nxt_max);
tr[p].cnt=tr[ls(p)].cnt+tr[rs(p)].cnt;
}
else if(tr[ls(p)].maxa>tr[rs(p)].maxa){
tr[p].nxt_max=max(tr[ls(p)].nxt_max,tr[rs(p)].maxa);
tr[p].cnt=tr[ls(p)].cnt;
}
else{
tr[p].nxt_max=max(tr[rs(p)].nxt_max,tr[ls(p)].maxa);
tr[p].cnt=tr[rs(p)].cnt;
}
}
void f(int p,int a,int b,int c,int d){
tr[p].sum+=a*tr[p].cnt+c*(tr[p].len-tr[p].cnt);
tr[p].maxb=max(tr[p].maxb,tr[p].maxa+b);
tr[p].add_b=max(tr[p].add_b,tr[p].add_a+b);
tr[p].add_b1=max(tr[p].add_b1,tr[p].add_a1+d);
tr[p].add_a+=a;
tr[p].maxa+=a;
tr[p].add_a1+=c;
if(tr[p].nxt_max!=-inf){
tr[p].nxt_max+=c;
}
}
void push_down(int p){
int mx=max(tr[ls(p)].maxa,tr[rs(p)].maxa);
if(tr[ls(p)].maxa==mx){
f(ls(p),tr[p].add_a,tr[p].add_b,tr[p].add_a1,tr[p].add_b1);
}
else{
f(ls(p),tr[p].add_a1,tr[p].add_b1,tr[p].add_a1,tr[p].add_b1);
}
if(tr[rs(p)].maxa==mx){
f(rs(p),tr[p].add_a,tr[p].add_b,tr[p].add_a1,tr[p].add_b1);
}
else{
f(rs(p),tr[p].add_a1,tr[p].add_b1,tr[p].add_a1,tr[p].add_b1);
}
tr[p].add_a1=tr[p].add_a=tr[p].add_b1=tr[p].add_b=0;
}
void build(int p,int l,int r){
tr[p].len=r-l+1;
if(l==r){
tr[p].maxa=tr[p].maxb=tr[p].sum=a[l];
tr[p].nxt_max=-inf;
tr[p].cnt=1;
return;
}
int mid=(l+r)>>1;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
void add(int p,int l,int r,int q_l,int q_r,int val){
if(q_l<=l&&r<=q_r){
f(p,val,val,val,val);
return;
}
push_down(p);
int mid=(l+r)>>1;
if(q_l<=mid){
add(ls(p),l,mid,q_l,q_r,val);
}
if(q_r>mid){
add(rs(p),mid+1,r,q_l,q_r,val);
}
push_up(p);
}
void update_min(int p,int l,int r,int q_l,int q_r,int val){
if(tr[p].maxa<=val){
return;
}
if(q_l<=l&&r<=q_r&&val>=tr[p].nxt_max){
f(p,val-tr[p].maxa,val-tr[p].maxa,0,0);
return;
}
int mid=(l+r)>>1;
push_down(p);
if(q_l<=mid){
update_min(ls(p),l,mid,q_l,q_r,val);
}
if(q_r>mid){
update_min(rs(p),mid+1,r,q_l,q_r,val);
}
push_up(p);
}
int query_sum(int p,int l,int r,int q_l,int q_r){
if(q_l<=l&&r<=q_r){
return tr[p].sum;
}
int mid=(l+r)>>1,res=0;
push_down(p);
if(q_l<=mid){
res=res+query_sum(ls(p),l,mid,q_l,q_r);
}
if(q_r>mid){
res=res+query_sum(rs(p),mid+1,r,q_l,q_r);
}
return res;
}
int query_maxa(int p,int l,int r,int q_l,int q_r){
if(q_l<=l&&r<=q_r){
return tr[p].maxa;
}
int mid=(l+r)>>1;
int res=-inf;
push_down(p);
if(q_l<=mid){
res=max(query_maxa(ls(p),l,mid,q_l,q_r),res);
}
if(q_r>mid){
res=max(query_maxa(rs(p),mid+1,r,q_l,q_r),res);
}
return res;
}
int query_maxb(int p,int l,int r,int q_l,int q_r){
if(q_l<=l&&r<=q_r){
return tr[p].maxb;
}
int mid=(l+r)>>1;
push_down(p);
int res=-inf;
if(q_l<=mid){
res=max(query_maxb(ls(p),l,mid,q_l,q_r),res);
}
if(q_r>mid){
res=max(query_maxb(rs(p),mid+1,r,q_l,q_r),res);
}
return res;
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(q);
for(int i=1;i<=n;i++){
read(a[i]);
}
Seg_Tree::build(1,1,n);
for(int i=1;i<=q;i++){
int opt,l,r;
read(opt),read(l),read(r);
if(opt==1){
int val=0;
read(val);
Seg_Tree::add(1,1,n,l,r,val);
}
else if(opt==2){
int val;
read(val);
Seg_Tree::update_min(1,1,n,l,r,val);
}
else if(opt==3){
write_endl(Seg_Tree::query_sum(1,1,n,l,r));
}
else if(opt==4){
write_endl(Seg_Tree::query_maxa(1,1,n,l,r));
}
else{
write_endl(Seg_Tree::query_maxb(1,1,n,l,r));
}
}
return 0;
}
线段树合并/分裂
因为线段树分裂时往往还需要合并操作，所以就一起写好了。
线段树合并/分裂往往配合着权值线段树和动态开点线段树使用，用于维护集合信息。
为什么是动态开点线段树？这里等下在讲。
线段树合并的方法是很暴力的。设当前合并的是子树 \(x,y\)，如果有任意一个节点为零，返回另一个节点，否则整合 \(x,y\) 的信息，并分别合并 \(x,y\) 的左右儿子，可以发现一次合并的复杂度为 \(O(\text{两棵树重合的节点数})\)。
现在回到开始那个问题，为什么线段树合并常配合动态开点线段树使用，非常显然的是如果是普通线段树，那么两棵树一定都是满的，这时候合并的复杂度还不如重构。
所以线段树合并总复杂度分析时不是单次合并的操作复杂度，而是考虑合并 \(n\) 棵树，每棵树仅有一个位置有值，这样每次合并最多有 \(\log n\) 个点重复，总复杂度为 \(O(n\log n)\)。
线段树分裂则很像 FHQ-treap 的分裂，有按值分裂和按排名分裂两种。
对于按排名分裂，令 \(x\) 为当前要分裂的节点，\(y\) 表示分裂出来的节点，\(val_x\) 表示 \(x\) 子树中数的个数，\(k\) 为树 \(x\) 中保留排名小于等于 \(k\) 的数，\(ls_x,rs_x\) 分别表示 \(x\) 的左右儿子。
- 若 \(k>val_{ls_x}\)，令 \(k=k-val_{ls_x}\)，向右递归。
- 若 \(k\le val_{ls_x}\)，将 \(rs_x\) 赋给 \(rs_y\) 并清空 \(rs_x\)。
- 若 \(val_{ls_x}>k\)，再向左递归。
对于按值分裂，因为是值域线段树，所以可以令区间 \(\left[l,r\right]\) 表示要分裂的点 \(x\)，\(mid\) 表示区间中点，\(k\) 表示 \(x\) 中保留小于等于 \(k\) 的数。
- 若 \(k>mid\)，向右递归。
- 若 \(k\le mid\)，将 \(rs_x\) 赋给 \(rs_y\) 并清空 \(rs_x\)
- 若 \(mid>k\)，向左递归。
可以发现无论哪种分裂，每次分裂最多产生 \(\log n\) 个新点，复杂度为 \(O(n\log n)\)。
那么对于第一个操作可以分为三步：先在线段树 \(x\) 上分裂出区间 \(\left[x,n\right]\)，令这颗线段树为 \(y\)；在线段树 \(y\) 上分裂出区间 \(\left[y+1,n\right]\)，令这颗线段树为 \(z\)；最后将线段树 \(x\) 和 \(z\)合并。
点击查看代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10;
int n,m,tot,top,cnt=1,Stack[N<<5],ch[N<<5][2],val[N<<5],root[N];
int newnode(){
return top?Stack[top--]:++tot;
}
#define ls(p) ch[p][0]
#define rs(p) ch[p][1]
void del(int p){
Stack[++top]=p;
ls(p)=rs(p)=val[p]=0;
}
void update(int &p,int l,int r,int pos,int Val){
if(!p){
p=newnode();
}
val[p]+=Val;
if(l==r)return;
int mid=(l+r)>>1;
if(pos<=mid){
update(ls(p),l,mid,pos,Val);
}
else{
update(rs(p),mid+1,r,pos,Val);
}
}
int query(int p,int l,int r,int posl,int posr){
if(posl<=l&&r<=posr){
return val[p];
}
int mid=(l+r)>>1,res=0;
if(posl<=mid){
res+=query(ls(p),l,mid,posl,posr);
}
if(posr>mid){
res+=query(rs(p),mid+1,r,posl,posr);
}
return res;
}
int get_kth(int p,int l,int r,int k){
if(l==r){
return l;
}
int mid=(l+r)>>1;
if(val[ls(p)]>=k){
return get_kth(ls(p),l,mid,k);
}
else{
return get_kth(rs(p),mid+1,r,k-val[ls(p)]);
}
}
int merge(int x,int y){
if(!x||!y){
return x+y;
}
val[x]+=val[y];
ls(x)=merge(ls(x),ls(y));
rs(x)=merge(rs(x),rs(y));
del(y);
return x;
}
void split(int x,int &y,int k){
if(!x){
return;
}
y=newnode();
int Val=val[ls(x)];
if(k>Val){
split(rs(x),rs(y),k-Val);
}
else{
swap(rs(x),rs(y));
}
if(k<Val){
split(ls(x),ls(y),k);
}
val[y]=val[x]-k;
val[x]=k;
}
int read(){
int s=0,f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
s=s*10+(ch-'0');
ch=getchar();
}
return s*f;
}
signed main(){
int n,m,x,y,z,opt;
n=read(),m=read();
for(int i=1;i<=n;i++){
x=read();
update(root[1],1,n,i,x);
}
for(int i=1;i<=m;i++){
opt=read();
if(!opt){
x=read(),y=read(),z=read();
int Val=query(root[x],1,n,1,z),V=query(root[x],1,n,y,z);
int tmp=0;
split(root[x],root[++cnt],Val-V);
split(root[cnt],tmp,V);
root[x]=merge(root[x],tmp);
}
else if(opt==1){
x=read(),y=read();
root[x]=merge(root[x],root[y]);
}
else if(opt==2){
x=read(),y=read(),z=read();
update(root[x],1,n,z,y);
}
else if(opt==3){
x=read(),y=read(),z=read();
printf("%lld\n",query(root[x],1,n,y,z));
}
else{
x=read(),y=read();
if(val[root[x]]<y){
puts("-1");
}
else{
printf("%lld\n",get_kth(root[x],1,n,y));
}
}
}
return 0;
}
线段树分治
按照理解来说，线段树分治其实和线段树并没有线段树有特别大的关系，我更愿意将其理解为一个套了个线段树皮的分治，它长得更像整体二分/CDQ分治。实际上来说，它也只用了线段树具有分治结构这个特点。
线段树分治的操作为建一颗以时间为坐标的线段树，如果某次修改完全包含区间 \(\left[l,r\right]\)，则将这次修改挂在代表区间 \(\left[l,r\right]\) 的点 \(x\) 上。最后询问时，同样按时间分治求答案，先修改当前节点，处理当前节点的信息，再根据维护的数据结构的性质，将修改的信息传下去（需要注意的是子节点询问完后记得删除修改，放置对后续节点造成影响）/到了儿子后再重构。
二分图的判断有一个很简便的用种类并查集判断的方法，所以可以用线段树分治维护并查集。因为要删除修改，所以不能用路径压缩，只能用按秩合并。因为后面的询问必然用到前面修改的信息，所以将信息传下去，等儿子节点询问完成后，再进行删除。
点击查看代码
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define pdi pair<double,int>
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define eps 1e-9
using namespace std;
namespace IO{
template<typename T>
inline void read(T &x){
x=0;
int f=1;
char ch=getchar();
while(ch>'9'||ch<'0'){
if(ch=='-'){
f=-1;
}
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+(ch-'0');
ch=getchar();
}
x=(f==1?x:-x);
}
template<typename T>
inline void write(T x){
if(x<0){
putchar('-');
x=-x;
}
if(x>=10){
write(x/10);
}
putchar(x%10+'0');
}
template<typename T>
inline void write_endl(T x){
write(x);
putchar('\n');
}
template<typename T>
inline void write_space(T x){
write(x);
putchar(' ');
}
}
using namespace IO;
const int N=2e5+10;
int n,m,k;
vector<int>num[N<<2];
struct edge{
int u,v;
}e[N<<1];
int ls(int p){
return p<<1;
}
int rs(int p){
return p<<1|1;
}
void ins(int p,int l,int r,int q_l,int q_r,int id){
if(q_l<=l&&r<=q_r){
num[p].pb(id);
return;
}
int mid=(l+r)>>1;
if(q_l<=mid){
ins(ls(p),l,mid,q_l,q_r,id);
}
if(q_r>mid){
ins(rs(p),mid+1,r,q_l,q_r,id);
}
}
stack<pii>st;
int fa[N<<1],siz[N<<1];
int getfa(int x){
while(fa[x]!=x){
x=fa[x];
}
return x;
}
void merge(int u,int v){
if(u==v){
return;
}
if(siz[u]>siz[v]){
swap(u,v);
}
st.push(mp(u,siz[u]));
fa[u]=v;
siz[v]+=siz[u];
}
void query(int p,int l,int r){
bool flag=1;
int Siz=st.size();
for(auto x:num[p]){
int u=getfa(e[x].u),v=getfa(e[x].v);
if(u==v){
for(int i=l;i<=r;i++){
puts("No");
}
flag=0;
break;
}
merge(getfa(e[x].u+n),v);
merge(getfa(e[x].v+n),u);
}
if(flag){
if(l==r){
puts("Yes");
}
else{
int mid=(l+r)>>1;
query(ls(p),l,mid);
query(rs(p),mid+1,r);
}
}
while(st.size()>Siz){
pii x=st.top();
st.pop();
siz[fa[x.first]]-=x.second;
fa[x.first]=x.first;
}
}
signed main(){
#ifndef ONLINE_JUDGE
freopen("1.in","r",stdin);
freopen("1.out","w",stdout);
#endif
read(n),read(m),read(k);
for(int i=1;i<=2*n;i++){
fa[i]=i;
siz[i]=1;
}
for(int i=1;i<=m;i++){
int l,r;
read(e[i].u),read(e[i].v),read(l),read(r);
if(l!=r){
ins(1,1,k,l+1,r,i);
}
}
query(1,1,k);
return 0;
}