挺妙的思想,线段树不仅仅是一种数据结构,还是一种处理问题的思想,在图论的建图等方面也有用到。

这个方法全称应该叫“线段树对时间CDQ分治”,用于处理有时间参数的修改与询问问题。但是有一个前提,就是一个时间区间的修改可以分成互不影响的两个时间区间的修改,比如这题的边(u,v,start,end)可以分裂为(u,v,start,mid)和(u,v,mid+1,end)。

这题听说LCT可做,但还有一种思路,CDQ(L,R,A)表示询问在[L,R]中,关于这个询问(且还未被处理)的修改集合为A的分治过程。具体流程是:

1.遍历A,对于所有完全包含[L,R]的修改操作进行处理。

2.将A中所有不完全包含[L,R]的修改操作按照线段树的分法分到包含[L,mid]和[mid+1,R]的两个区间中,用集合B和C记录这些修改。

3.分别递归[L,mid]和[mid+1,R],如果L=R则可以直接特判回溯。

4.撤销本层所有操作,保证后续回溯与递归正确进行。

回到这一题,所谓修改就是记录距离的并查集操作(因为判断二分图的方法就是查找里面是否有奇环),所以这里的并查集必须支持撤销,不能路径压缩。总复杂度$O(n\log^2 n)$

 #include<cstdio>
#include<vector>
#include<algorithm>
#define rep(i,l,r) for (int i=l; i<=r; i++)
typedef long long ll;
using namespace std; const int N=;
int n,m,T,u,v,l,r,top;
struct E{int u,v,l,r; bool operator<(const E &a)const{ return (l==a.l)?r<a.r:l<a.l; } };
vector<E> a;
struct P{ int fa,val,sz; }t[N];
struct D{ int x,y; P a,b; }stk[N]; void init(){ rep(i,,n) t[i]=(P){i,,}; }
int find(int x){ while (t[x].fa!=x) x=t[x].fa; return x;}
int dis(int x){
int res=;
while (t[x].fa!=x) res^=t[x].val,x=t[x].fa;
return res;
} void link(int x,int y){
int val=dis(x)^dis(y)^;
x=find(x); y=find(y);
stk[++top]=(D){x,y,t[x],t[y]};
if (t[x].sz>t[y].sz) swap(x,y);
t[x].fa=y; t[x].val=val; t[y].sz+=t[x].sz;
} void recov(int k){ while (top!=k) t[stk[top].x]=stk[top].a,t[stk[top].y]=stk[top].b,top--; } void CDQ(int L,int R,vector<E> &a){
int mid=(L+R)>>,bot=top;
vector<E> b,c;
for (int i=; i<(int)a.size(); i++){
E now=a[i]; int x=now.u,y=now.v;
if (now.l==L && now.r==R){
int p=find(x),q=find(y);
if (p==q){
int val=dis(x)^dis(y);
if (val==){
rep(i,L,R) puts("No");
recov(bot); return;
}
}else link(x,y);
}else if (now.r<=mid) b.push_back(now);
else if (now.l>mid) c.push_back(now);
else b.push_back((E){now.u,now.v,now.l,mid}),c.push_back((E){now.u,now.v,mid+,now.r});
}
if (L==R) puts("Yes"); else CDQ(L,mid,b),CDQ(mid+,R,c);
recov(bot);
} int main(){
freopen("bzoj4025.in","r",stdin);
freopen("bzoj4025.out","w",stdout);
scanf("%d%d%d",&n,&m,&T);
rep(i,,m){
scanf("%d%d%d%d",&u,&v,&l,&r); l++;
if (l<=r) a.push_back((E){u,v,l,r});
}
init(); CDQ(,T,a);
return ;
}
05-02 12:41
查看更多