1.一种数据结构，一般用于有撤销操作，并且不好处理撤销的题目中。这个时候对时间建立线段树，将每个修改和询问插入对应时间内，对每个线段树节点进行处理就可以保证时间复杂度为 \( \O (nlogn) \) 。
2.例题
（1）
题意:给出n个点，m条边，每条边从时间l出现，r消失，求每个时间图是否是二分图。
题解：
二分图的判定可以通过判断奇环来搞，判奇环可以使用扩展域并查集。
进行线段树分治，将每条边插入对应时间的节点vector中，到了一个节点后使用可撤销并查集将所有该节点的的边处理了，递归结束时将边的贡献撤销即可。（使用一个栈记录每次操作前的状态）。
代码如下：
#include<bits/stdc++.h> using namespace std; const int N=2e5+5; int k,n,m,fa[N],u[N],v[N],dep[N]; vector <int> ve[N<<1]; struct pigu { int xp,shu; pigu(int x=0,int y=0) { shu=x;xp=y; } }; inline int read() { char c=getchar(); int x=0,f=1; while(!isdigit(c)) {if(c==‘-‘) f=-1;c=getchar();} while(isdigit(c)) {x=(x<<3)+(x<<1)+c-‘0‘;c=getchar();} return x*f; } inline void insert(int now,int l,int r,int L,int R,int jia) { if(l>=L&&r<=R) { ve[now].push_back(jia); return; } int mid=(l+r)>>1; if(L<=mid) insert(now<<1,l,mid,L,R,jia); if(R>=mid+1) insert(now<<1|1,mid+1,r,L,R,jia); } stack <pigu> st; inline int find(int x) { if(x==fa[x]) return x; return find(fa[x]); } inline void merge(int x,int y) { if(x==y) return; if(dep[x]<dep[y]) swap(x,y); st.push(pigu(y,dep[x]==dep[y])); fa[y]=x;dep[x]+=(dep[x]==dep[y]); } inline void get_ans(int now,int l,int r) { bool pan=0; int len=ve[now].size(),hu=st.size(); for(int i=0;i<len;i++) { int fa1=find(u[ve[now][i]]),fa2=find(v[ve[now][i]]); if(fa1==fa2) { for(int j=l;j<=r;j++) cout<<"No\n"; pan=1; break; } merge(find(u[ve[now][i]]+n),fa2);merge(find(v[ve[now][i]]+n),fa1); } if(pan==0) { int mid=(l+r)>>1; if(l==r) cout<<"Yes\n"; else { get_ans(now<<1,l,mid); get_ans(now<<1|1,mid+1,r); } } while(st.size()>hu) { dep[fa[st.top().shu]]-=st.top().xp; fa[st.top().shu]=st.top().shu; st.pop(); } } int main() { n=read();m=read();k=read(); for(int i=1;i<=2*n;i++) fa[i]=i; for(int i=1,l,r;i<=m;i++) { u[i]=read();v[i]=read();l=read();r=read(); if(l<r) insert(1,1,k,l+1,r,i); } get_ans(1,1,k); }
原文：https://www.cnblogs.com/betablewaloot/p/12458000.html
