线段树分治
P5787 二分图 /【模板】线段树分治
题意：
一条边只会在某个时间段出现
询问每个时间段是否是二分图
思路：
二分图存在等于是否有奇数环，可以使用拓展域并查集判断
cpp
struct DSU{
vector<int> par,siz;
stack<int> st;
int tot=0;
DSU(){}
DSU(int n){
init(n);
}
void init(int n){
par.resize(n);
siz.assign(n,1);
iota(par.begin(),par.end(),0);
}
int find(int x){
return par[x]==x?x:find(par[x]);
}
bool merge(int x,int y,int op){
x=find(x),y=find(y);
if(x==y)return false;
if(siz[x]<siz[y])swap(x,y);
par[y]=x;
siz[x]+=siz[y];
if(op){
st.push(y);
tot++;
}
return true;
}
bool same(int x,int y){
return find(x)==find(y);
}
void del(){
if(!tot)return;
tot--;
int y=st.top();
st.pop();
siz[par[y]]-=siz[y];
par[y]=y;
}
void back(int t=0){
while(tot>t)del();
}
} dsu;
int n;
struct SegmentTree{
struct Node{
int l,r;
vector<array<int,2>> a;
};
vector<Node> t;
void init(int n){
t=vector<Node>(n<<2);
}
void build(int p,int l,int r){
t[p]={l,r};
if(l==r)return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void modify(int p,int l,int r,int x,int y){
if(l<=t[p].l&&r>=t[p].r){
t[p].a.push_back({x,y});
return;
}
int mid=t[p].l+t[p].r>>1;
if(l<=mid)modify(p<<1,l,r,x,y);
if(r>mid)modify(p<<1|1,l,r,x,y);
}
void dfs(int p,int l,int r){
bool g=0;
int tot=dsu.tot;
for(auto &[u,v]:t[p].a){
if(dsu.same(u,v)){
for(int i=l;i<=r;i++)cout<<"No\n";
g=1;
break;
}
dsu.merge(u,v+n,1);
dsu.merge(v,u+n,1);
}
if(!g){
if(l==r){
cout<<"Yes\n";
return;
}
int mid=l+r>>1;
dfs(p<<1,l,mid);
dfs(p<<1|1,mid+1,r);
}
dsu.back(tot);
}
} seg;
void solve(){
int m,k;
cin>>n>>m>>k;
seg.init(k);
seg.build(1,1,k);
dsu.init(2*n+1);
for(int i=1;i<=m;i++){
int x,y,l,r;
cin>>x>>y>>l>>r;
seg.modify(1,l+1,r,x,y);
}
seg.dfs(1,1,k);
}CF1140F
题意：
CF2069F
题意：
给定两个图A,B,每次操作可以删除或增加A，B的边，求每次询问后，A需要添加多少条边才能使得，B是A的子图
思路：
考虑A，B的联合图，那么A和B都是联合图的子图，答案即是A和联合图的连通块个数差
问题转化成求动态维护连通块问题，考虑线段树分治+可撤销并查集离线求解
cpp
struct DSU{
vector<int> par,siz;
stack<int> st;
int tot=0,cnt;
DSU(){}
DSU(int n){
init(n);
}
void init(int n){
back();
cnt=n-1;
par.resize(n);
siz.assign(n,1);
iota(par.begin(),par.end(),0);
}
int find(int x){
return par[x]==x?x:find(par[x]);
}
bool merge(int x,int y,int op){
x=find(x),y=find(y);
if(x==y)return false;
cnt--;
if(siz[x]<siz[y])swap(x,y);
par[y]=x;
siz[x]+=siz[y];
if(op){
st.push(y);
tot++;
}
return true;
}
bool same(int x,int y){
return find(x)==find(y);
}
void del(){
if(!tot)return;
tot--;
int y=st.top();
st.pop();
siz[par[y]]-=siz[y];
int p=par[y];
par[y]=y;
if(find(p)!=find(y))cnt++;
}
void back(int t=0){
while(tot>t)del();
}
} dsu;
struct SegmentTree{
struct Node{
int l,r;
vector<PII> v;
};
vector<Node> t;
SegmentTree(){}
SegmentTree(int n){
init(n);
}
void init(int n){
t=vector<Node>(n<<2);
}
void build(int p,int l,int r){
t[p]={l,r};
if(l==r)return;
int mid=l+r>>1;
build(p<<1,l,mid);
build(p<<1|1,mid+1,r);
}
void modify(int p,int l,int r,int x,int y){
if(l<=t[p].l&&t[p].r<=r){
t[p].v.push_back({x,y});
return;
}
int mid=t[p].l+t[p].r>>1;
if(l<=mid)modify(p<<1,l,r,x,y);
if(r>mid)modify(p<<1|1,l,r,x,y);
}
void dfs(int p,vector<int> &ans){
int ts=dsu.tot;
for(auto [x,y]:t[p].v){
dsu.merge(x,y,1);
}
if(t[p].l==t[p].r){
ans[t[p].l]=dsu.cnt;
}
else{
dfs(p<<1,ans);
dfs(p<<1|1,ans);
}
dsu.back(ts);
}
} seg;
void cal(vector<array<int,4>> &v,vector<int> &ans,int n,int time){
if(v.size()==0){
ans.assign(time+1,n);
}
dsu.init(n+1);
seg.init(time+1);
seg.build(1,1,time);
for(auto [l,r,x,y]:v){
seg.modify(1,l,r,x,y);
}
seg.dfs(1,ans);
}
void solve(){
int n,q;
cin>>n>>q;
map<PII,int> mp[2];
vector<array<int,4>> e[2];
for(int i=1;i<=q;i++){
char c;
int x,y;
cin>>c>>x>>y;
if(x>y)swap(x,y);
if(mp[c-'A'].count({x,y})){
e[c-'A'].push_back({mp[c-'A'][{x,y}],i-1,x,y});
mp[c-'A'].erase({x,y});
}
else mp[c-'A'][{x,y}]=i;
}
for(int i=0;i<2;i++){
for(auto [p,t]:mp[i]){
e[i].push_back({t,q,p.first,p.second});
}
}
vector<int> ans(q+1),res(q+1);
for(auto it:e[0])e[1].push_back(it);
cal(e[0],ans,n,q);
cal(e[1],res,n,q);
for(int i=1;i<=q;i++)cout<<ans[i]-res[i]<<"\n";
}