线段树分治
处理的问题
依次操作，有增加，删除，对时间点询问几种操作的问题。
有时候删除有限制（如可撤销并查集），所以就不考虑删除，只考虑每一个增加操作存在的时间范围。
有时候问题中没有明说删除，比如最小mex生成树，而是需要不使用某些边。
可撤销并查集
并查集可以按秩合并，合并/查询单次时间复杂度 \(O(\log N)\)。
可以用一个栈存上次合并的操作，撤销上一步的操作即将栈顶的依次合并取消，并弹出栈顶。
pair<int,int>merge(int x,int y){while(x!=Fa[x])x=Fa[x];while(y!=Fa[y])y=Fa[y];if(x==y)return {0,0};if(sz[x]<sz[y]){Fa[x]=y;sz[y]+=sz[x];return {x,y};}else{Fa[y]=x;sz[x]+=sz[y];return {y,x};}
}
stack<pair<int,int> >del;
void revoke(){pair<int,int>last=del.top();del.pop();int x=last.first,y=last.second;Fa[x]=x;sz[y]-=sz[x];
}
signed main(){//...del.push(merge(x,y));
}
写法
线段树分治中以时间作为下标，将每个操作存在的时间区间分为至多 \(\log N\) 个不重叠的小区间。
以动态图连通性为例，线段树上维护每条边的出现时间段。
由于询问的是时间点，所以找答案时必定会递归到叶子结点。
递归到线段树上一个点时，将这个点对应时间段的边加入并查集，离开时再删除，满足可撤销并查集只能删上一个的限制。
#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define endl putchar('\n')
#define psp putchar(' ')
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int N=2e5+5;
int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();return x*f;
}
void print(int x){if(x<0)putchar('-'),x=-x;if(x<10){putchar(x+'0');return;}print(x/10);putchar(x%10+'0');
}
void putstr(string s){for(int i=0;i<s.size();i++)putchar(s[i]);
}
int lowbit(int x){return x&-x;
}
int n,m,k;
int T;
struct node{int l,r;vector<pair<int,int> >add;
}f[4*N];
void build(int p,int l,int r){f[p]=node{l,r};f[p].add.clear();if(l==r)return;int mid=l+r>>1;build(lc,l,mid);build(rc,mid+1,r);
}
int sz[N];
int Fa[N];
void update(int p,int l,int r,int u,int v){if(l<=f[p].l&&f[p].r<=r){f[p].add.push_back({u,v});return;}int mid=f[p].l+f[p].r>>1;if(l<=mid)update(lc,l,r,u,v);if(r>mid)update(rc,l,r,u,v);
}
pair<int,int>merge(int x,int y){while(x!=Fa[x])x=Fa[x];while(y!=Fa[y])y=Fa[y];if(x==y)return {0,0};if(sz[x]<sz[y]){Fa[x]=y;sz[y]+=sz[x];return {x,y};}else{Fa[y]=x;sz[x]+=sz[y];return {y,x};}
}
int ans[N];
stack<pair<int,int> >del;
void dfs(int p,int is){int before=del.size();for(int i=0;i<f[p].add.size();i++){int u=f[p].add[i].first;int v=f[p].add[i].second;while(u!=Fa[u])u=Fa[u];while(v!=Fa[v])v=Fa[v];if(u==v)is=0;else{del.push(merge(u,v+n));del.push(merge(v,u+n));}}if(f[p].l==f[p].r){ans[f[p].l]=is;}else{dfs(lc,is);dfs(rc,is);}while(del.size()>before){int u=del.top().first;int v=del.top().second;Fa[u]=u;sz[v]-=sz[u];del.pop();}
}
signed main(){//ios::sync_with_stdio(0);n=read(),m=read(),k=read();build(1,1,k);for(int i=1;i<=2*n;i++)Fa[i]=i,sz[i]=1;while(m--){int u=read(),v=read(),l=read(),r=read();if(l>r)swap(l,r);if(l+1<=r)update(1,l+1,r,u,v);}dfs(1,1);for(int i=1;i<=k;i++){if(ans[i])putstr("Yes\n");else putstr("No\n");}
}
做题时
要先找到题目中的区间怎么分配，比如：在时间 \([L,R]\) 存在，其他时间不存在；在颜色为 \(C\) 时不存在，其余时间存在；在权值为 \(X\) 时不存在，其余存在……
自己遇到的问题
- 很久没写多不是动态开点的线段树了，线段树要记得
build。 - 栈记得
pop。 - 合并和撤销的时候两个点不要搞反了。