线段树分治

适用范围

对X的操作在一个时间段生效，询问一些时间点（或时间段）上的X的状态

核心操作

1.用时间段建一颗线段树，将操作放到对应的一些（或一个）结点上 2.遍历线段树，每进入一个节点就执行上面的操作，如果有询问就执行 3.退出结点时，撤销在这个结点上的操作

思想

面对上述问题时暴力的做法就是对每个时间点，遍历这个时间点上的所有操作，但是这样时间复杂度过高。考虑当我们已经算出时间点x的答案时，我们不需要撤销所有操作，只需要撤销在x+1失效的操作，即在x结束的操作。而对于在[x，y]生效的操作，只需要在算x的时候执行，在算完y的时候撤销即可。这些区间就可以放在线段树的结点上，进入结点就执行上面的操作，退出结点就撤销上面的操作. 时间复杂度：nlog(n)

代码

洛谷模板题P5787 ps:这题是线段树分治+可撤销并查集

#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define N 5000010 #define M 5010 #define ll long long using namespace std; struct B { int s,e; }way[N]; int n,m,cnt; int sta[N][4],f[N],w[N]; vector <int> ve[N]; int getf(int x) { while(f[x]!=x) x=f[x]; return x; } void merge(int a,int b) { int fa,fb; fa=getf(a); fb=getf(b); if(fa==fb) return; if(w[fa]<w[fb]) swap(fa,fb); cnt++; sta[cnt][0]=fa; sta[cnt][1]=w[fa]; sta[cnt][2]=fb; sta[cnt][3]=f[fb]; if(w[fa]==w[fb]) w[fa]++; f[fb]=fa; } void undo() { w[sta[cnt][0]]=sta[cnt][1]; f[sta[cnt][2]]=sta[cnt][3]; cnt--; } void add(int l,int r,int p,int s,int e,int x) { if(l>=s && r<=e) { ve[p].push_back(x); return; } if(l==r) return; int mid=l+r>>1; if(s<=mid) add(l,mid,p*2,s,e,x); if(mid<e) add(mid+1,r,p*2+1,s,e,x); } void deal(int l,int r,int p) { int fa,fb; for(int i=0,j;i<ve[p].size();i++) { j=ve[p][i]; merge(way[j].s,way[j].e); fa=getf(way[j].s); fb=getf(way[j].s^1); if(fa==fb) { for(int o=0;o<=i;o++) undo(); for(int o=l;o<=r;o++) printf("No\n"); return; } } if(l==r) { printf("Yes\n"); } else { int mid=l+r>>1; deal(l,mid,p*2); deal(mid+1,r,p*2+1); } for(int i=0,j;i<ve[p].size();i++) undo(); return; } int main() { int a,b,l,r,k; scanf("%d%d%d",&n,&m,&k); n=2*n+1; for(int i=1;i<=n;i++) f[i]=i; for(int i=1;i<=m;i++) { scanf("%d%d%d%d",&a,&b,&l,&r); a*=2; b*=2; if(l==r) continue; l++; way[i*2-1].s=a; way[i*2-1].e=b^1; add(1,k,1,l,r,i*2-1); way[i*2].s=a^1; way[i*2].e=b; add(1,k,1,l,r,i*2); } deal(1,k,1); return 0; }

线段树合并

适用条件

对于一个可分治的问题，每个子问题都要用线段树储存信息，而一个大问题的信息可由子问题的信息直接合并得到

核心操作

int merge(int x,int y,int l,int r)//线段树合并操作 { if(!x || !y) return x|y;//如果有一个是0，返回另一个 if(l==r) { key[x]+=key[y];//结点的合并 return x; } int mid=l+r>>1; son[x][0]=merge(son[x][0],son[y][0],l,mid); son[x][1]=merge(son[x][1],son[y][1],mid+1,r); up(x);//更新x的信息 return x; }

要点

每个最小问题的结点生成一颗线段树，但是要用插新节点生成（类似主席树），不能直接生成一颗完全二叉树，否则空间会爆、合并时相当于线段树前驱遍历，可以利用这一点来维护信息时间复杂度：如果插入了n个点，合并时间复杂度就是nlog(n)

代码

洛谷模板题P4556

ps 这题是线段树合并+树上差分+lca

#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define N 1010 #define M 2010 #define ll long long using namespace std; struct A { int e,nxt; }way[N*2]; int n,m,top,ans[N],lef=INF,rig=0,k; int dpt[N],dp[N][30],lg[N]; int edge,wout[N]; int tree[M],key[M],son[M][2],head[N]; int aa[N],bb[N],cc[N]; void add(int &s,int &e) { edge++; way[edge].e=e; way[edge].nxt=wout[s]; wout[s]=edge; } void lca_dfs(int x) { dpt[x]=dpt[dp[x][0]]+1; for(int i=1;i<=lg[dpt[x]]+1;i++) dp[x][i]=dp[dp[x][i-1]][i-1]; for(int i=wout[x];i;i=way[i].nxt) { if(way[i].e!=dp[x][0]) { dp[way[i].e][0]=x; lca_dfs(way[i].e); } } } int lca(int x,int y) { if(dpt[x]<dpt[y]) swap(x,y); while(dpt[x]>dpt[y]) x=dp[x][lg[dpt[x]-dpt[y]]]; if(x==y) return x; for(int i=lg[dpt[x]];i>=0;i--) { if(dp[x][i]!=dp[y][i]) { x=dp[x][i]; y=dp[y][i]; } } return dp[x][0]; } void up(int &x) { if(son[x][0] && son[x][1]) { if(key[son[x][0]]>=key[son[x][1]]) key[x]=key[son[x][0]],tree[x]=tree[son[x][0]]; else key[x]=key[son[x][1]],tree[x]=tree[son[x][1]]; } else if(son[x][0]) key[x]=key[son[x][0]],tree[x]=tree[son[x][0]]; else key[x]=key[son[x][1]],tree[x]=tree[son[x][1]]; } void ins(int l,int r,int &now,int pos,int val) { if(now==0) { now=++top; tree[now]=0; key[now]=0; son[now][0]=son[now][1]=0; } if(l==r) { key[now]+=val; tree[now]=l; return; } int mid=l+r>>1; if(pos<=mid) ins(l,mid,son[now][0],pos,val); else ins(mid+1,r,son[now][1],pos,val); up(now); } int merge(int x,int y,int l,int r) { if(!x || !y) return x|y; if(l==r) { key[x]+=key[y]; return x; } int mid=l+r>>1; son[x][0]=merge(son[x][0],son[y][0],l,mid); son[x][1]=merge(son[x][1],son[y][1],mid+1,r); up(x); return x; } void deal(int x) { for(int i=wout[x];i;i=way[i].nxt) { if(way[i].e!=dp[x][0]) { deal(way[i].e); head[x]=merge(head[x],head[way[i].e],lef,rig); } } if(key[head[x]]) ans[x]=tree[head[x]]; else ans[x]=0; } int main() { int a,b; scanf("%d%d",&n,&m); for(int i=1;i<n;i++) { scanf("%d%d",&a,&b); add(a,b); add(b,a); } for(int i=1,k=2,l=0;i<=n;i++) { if(i==k) { k*=2; l++; } lg[i]=l; } dp[1][0]=1; lca_dfs(1); for(int i=1;i<=m;i++) { scanf("%d%d%d",&aa[i],&bb[i],&cc[i]); lef=min(lef,cc[i]); rig=max(rig,cc[i]); } for(int i=1;i<=m;i++) { k=lca(aa[i],bb[i]); ins(lef,rig,head[aa[i]],cc[i],1); ins(lef,rig,head[bb[i]],cc[i],1); ins(lef,rig,head[k],cc[i],-1); if(k!=1) ins(lef,rig,head[dp[k][0]],cc[i],-1); } deal(1); for(int i=1;i<=n;i++) printf("%d\n",ans[i]); return 0; }