題目大意：
一個n個節點的圖 T時間内一些邊會出現後消失 求出每一時間段内這個圖是否是二分圖
思路：
對于每條邊 線上段樹中修改這個邊所影響的區間 使用帶撤銷按秩合并并查集
用一個數組來維護每個點到根路徑長度的奇偶性（這個數組非常的nb
線段樹分治即相當于pushdown了一堆影響 對于每個點查詢即可
1 #include<iostream>
2 #include<cstdlib>
3 #include<cstdio>
4 #include<cmath>
5 #include<algorithm>
6 #include<string>
7 #include<queue>
8 #include<vector>
9 #include<map>
10 #define rep(i,s,t) for(register int i=(s);i<=(t);++i)
11 #define dwn(i,s,t) for(register int i=(s);i>=(t);--i)
12 #define ren(x) for(register int i=fst[x];i;i=nxt[i])
13 #define Fill(x,t) memset(x,t,sizeof(x))
14 #define ll long long
15 #define inf 2139062143
16 #define MAXN 500100
17 using namespace std;
18 inline int read()
19 {
20 int x=0,f=1;char ch=getchar();
21 while(!isdigit(ch)) {if(ch=='-') f=-1;ch=getchar();}
22 while(isdigit(ch)) {x=x*10+ch-'0';ch=getchar();}
23 return x*f;
24 }
25 int n,m,T,rnk[MAXN],fa[MAXN],top,fst[MAXN<<2],nxt[MAXN<<3],to[MAXN<<3],cnt;
26 int s[MAXN],t[MAXN],val[MAXN];
27 inline void add(int u,int v) {nxt[++cnt]=fst[u],fst[u]=cnt,to[cnt]=v;}
28 struct Edge{int u,v,rnk;}st[MAXN];
29 int find(int x) {return x==fa[x]?x:find(fa[x]);}
30 inline void merge(int u,int v,int w)
31 {
32 int x=find(u),y=find(v);
33 if(rnk[x]<rnk[y]) swap(x,y);
34 fa[y]=x,st[++top]=(Edge){x,y,rnk[x]},val[y]=w;
35 if(rnk[x]==rnk[y]) rnk[x]++;
36 }
37 inline void dlt() {fa[st[top].v]=st[top].v,rnk[st[top].u]=st[top].rnk,val[st[top--].v]=0;}
38 inline int dis(int x,int res=0) {for(;fa[x]!=x;x=fa[x]) res^=val[x];return res;}
39 void mdf(int k,int l,int r,int a,int b,int w)
40 {
41 if(l==a&&r==b) {add(k,w);return ;}
42 int mid=l+r>>1;
43 if(b<=mid) mdf(k<<1,l,mid,a,b,w);
44 else if(a>mid) mdf(k<<1|1,mid+1,r,a,b,w);
45 else {mdf(k<<1,l,mid,a,mid,w);mdf(k<<1|1,mid+1,r,mid+1,b,w);}
46 }
47 void solve(int k,int l,int r,int ok)
48 {
49 int mid=l+r>>1,tmp,pos=top;
50 if(!ok) {rep(i,l,r) puts("No");return ;}
51 ren(k) {tmp=dis(s[to[i]])^dis(t[to[i]])^1;if(find(s[to[i]])!=find(t[to[i]])) merge(s[to[i]],t[to[i]],tmp);else if(tmp) ok=0;}
52 if(l==r) {puts(ok?"Yes":"No");return ;}
53 solve(k<<1,l,mid,ok);solve(k<<1|1,mid+1,r,ok);
54 while(top!=pos) dlt();
55 }
56 int main()
57 {
58 n=read(),m=read(),T=read();int c,d;rep(i,1,n) fa[i]=i;
59 rep(i,1,m) {s[i]=read(),t[i]=read(),c=read(),d=read();if(c<d) mdf(1,1,T,c+1,d,i);}
60 solve(1,1,T,1);
61 } View Code
轉載于:https://www.cnblogs.com/yyc-jack-0920/p/10026886.html