支持加边和删边的二分图判定，分治并查集水之(表示我的LCT还很不熟……仅仅停留在极其简单的模板水平)。
由于是带权并查集，并且不能路径压缩，所以对权值(到父亲距离的奇偶性)的维护要注意一下。
有一个小优化：如果当前图已经不是二分图就不再继续dfs线段树，直接把区间内的每个答案设为No后回溯即可。
这次写了个按size合并，不过随机合并比按size合并还快一点是什么鬼……
按size合并的代码：
/************************************************************** Problem: 4025 User: hzoier Language: C++ Result: Accepted Time:13616 ms Memory:39288 kb ****************************************************************/ #include<cstdio> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int maxn=100010; void addedge(int,int,int); void solve(int,int,int); bool mergeset(int,int,vector<int>&); void cut(int); int prt[maxn],size[maxn]; bool d[maxn]={false}; int n,m,e,x,y,s,t; vector<int>u[maxn<<2],v[maxn<<2]; int main(){ scanf("%d%d%d",&n,&e,&m); for(int i=1;i<=n;i++){ prt[i]=i; size[i]=1; } while(e--){ scanf("%d%d%d%d",&x,&y,&s,&t); s++; addedge(1,m,1); } solve(1,m,1); return 0; } void addedge(int l,int r,int rt){ if(s<=l&&t>=r){ u[rt].push_back(x); v[rt].push_back(y); return; } int mid=(l+r)>>1; if(s<=mid)addedge(l,mid,rt<<1); if(t>mid)addedge(mid+1,r,rt<<1|1); } void solve(int l,int r,int rt){ vector<int>stk; bool ok=true; for(int i=0;i<(int)u[rt].size();i++)if(mergeset(u[rt][i],v[rt][i],stk)){ for(int j=l;j<=r;j++)printf("No "); ok=false; break; } if(ok){ if(l==r)printf("Yes "); else{ int mid=(l+r)>>1; solve(l,mid,rt<<1); solve(mid+1,r,rt<<1|1); } } if(!stk.empty())for(int i=(int)stk.size()-1;i>=0;i--)cut(stk[i]); } bool mergeset(int x,int y,vector<int>&a){ bool dx=false,dy=false; int rx=x,ry=y; while(prt[rx]!=rx){ dx^=d[rx]; rx=prt[rx]; } while(prt[ry]!=ry){ dy^=d[ry]; ry=prt[ry]; } if(rx==ry)return dx==dy; if(size[rx]>size[ry])swap(rx,ry); prt[rx]=ry; size[ry]+=size[rx]; d[rx]=dx==dy; a.push_back(rx); return false; } void cut(int x){ int y=prt[x]; while(prt[y]!=y){ size[y]-=size[x]; y=prt[y]; } size[y]-=size[x]; prt[x]=x; d[x]=false; }
随机合并的代码(其实两份代码差别并不大)：
1 /************************************************************** 2 Problem: 4025 3 User: hzoier 4 Language: C++ 5 Result: Accepted 6 Time:13104 ms 7 Memory:38896 kb 8 ****************************************************************/ 9 10 #include<cstdio> 11 #include<cstring> 12 #include<algorithm> 13 #include<vector> 14 using namespace std; 15 inline int randint(){ 16 static int a=641,b=61213,c=34179277,x=1894872,p=998244353; 17 x=a*x*x+b*x+c;x%=p; 18 return x<0?(x=-x):x; 19 } 20 const int maxn=100010; 21 void addedge(int,int,int); 22 void solve(int,int,int); 23 bool mergeset(int,int,vector<int>&); 24 int prt[maxn]; 25 bool d[maxn]={false}; 26 int n,m,e,x,y,s,t; 27 vector<int>u[maxn<<2],v[maxn<<2]; 28 int main(){ 29 scanf("%d%d%d",&n,&e,&m); 30 for(int i=1;i<=n;i++)prt[i]=i; 31 while(e--){ 32 scanf("%d%d%d%d",&x,&y,&s,&t); 33 s++; 34 addedge(1,m,1); 35 } 36 solve(1,m,1); 37 return 0; 38 } 39 void addedge(int l,int r,int rt){ 40 if(s<=l&&t>=r){ 41 u[rt].push_back(x); 42 v[rt].push_back(y); 43 return; 44 } 45 int mid=(l+r)>>1; 46 if(s<=mid)addedge(l,mid,rt<<1); 47 if(t>mid)addedge(mid+1,r,rt<<1|1); 48 } 49 void solve(int l,int r,int rt){ 50 vector<int>stk; 51 bool ok=true; 52 for(int i=0;i<(int)u[rt].size();i++)if(mergeset(u[rt][i],v[rt][i],stk)){ 53 for(int j=l;j<=r;j++)printf("No "); 54 ok=false; 55 break; 56 } 57 if(ok){ 58 if(l==r)printf("Yes "); 59 else{ 60 int mid=(l+r)>>1; 61 solve(l,mid,rt<<1); 62 solve(mid+1,r,rt<<1|1); 63 } 64 } 65 if(!stk.empty())for(int i=(int)stk.size()-1;i>=0;i--){ 66 prt[stk[i]]=stk[i]; 67 d[i]=false; 68 } 69 } 70 bool mergeset(int x,int y,vector<int>&a){ 71 bool dx=false,dy=false; 72 int rx=x,ry=y; 73 while(prt[rx]!=rx){ 74 dx^=d[rx]; 75 rx=prt[rx]; 76 } 77 while(prt[ry]!=ry){ 78 dy^=d[ry]; 79 ry=prt[ry]; 80 } 81 if(rx==ry)return dx==dy; 82 if(randint()&1)swap(rx,ry); 83 prt[rx]=ry; 84 d[rx]=dx==dy; 85 a.push_back(rx); 86 return false; 87 }
感觉越来越忧伤，却没有办法排解，唉……