BZOJ 4025: 二分图

这个题嘛，分治线段树可以做啦…但是我并不想写…毕竟并查集还不能路径压缩只能按质合并…所以，我觉得还是写LCT比较友善…

LCT维护最晚删除…总体上就是说，从这个树上下来的边，要么消失，要么永远都不会再上来…这样，我们考虑按时间顺序枚举，该加边加边，该删边删边，只是多了如果新边不是树边的话，就和树边比较一下谁更晚删除，之后要么替换，要么滚蛋…之后维护一个num数组表示在第ii分钟的时候，导致不是二分图的边少num[i]个，另外维护现在有多少个这样的边…如果是0就是二分图，反之则不是…

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            using namespace std;#define N 400005#define ls ch[rt][0]#define rs ch[rt][1]#define get(rt) (ch[f[rt]][0]!=rt)#define isroot(rt) (ch[f[rt]][0]!=rt&&ch[f[rt]][1]!=rt)#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)char buf[1000000],*p1,*p2;int rd(){ register int x=0;register char c=nc(); while(c<'0'||c>'9')c=nc(); while(c>='0'&&c<='9')x=(((x<<2)+x)<<1)+c-'0',c=nc(); return x;}struct node{int x,y,l,r;}a[N];int ch[N][2],f[N],m,siz[N],mx[N],val[N],num[N],rev[N],n,Q,sum,now;void PushUp(int rt){siz[rt]=siz[ls]+siz[rs]+1;mx[rt]=rt;if(val[mx[rt]]>val[mx[ls]])mx[rt]=mx[ls];if(val[mx[rt]]>val[mx[rs]])mx[rt]=mx[rs];}void rotate(int rt){ int x=f[rt],y=f[x],k=get(rt); if(!isroot(x))ch[y][ch[y][0]!=x]=rt; ch[x][k]=ch[rt][!k];f[ch[x][k]]=x; ch[rt][!k]=x;f[x]=rt;f[rt]=y;PushUp(x);PushUp(rt);}void PushDown(int rt){if(rev[rt])swap(ch[ls][0],ch[ls][1]),swap(ch[rs][0],ch[rs][1]),rev[rt]=0,rev[ls]^=1,rev[rs]^=1;}void Update(int rt){if(!isroot(rt))Update(f[rt]);PushDown(rt);}void Splay(int rt){for(Update(rt);!isroot(rt);rotate(rt))if(!isroot(f[rt]))rotate(get(f[rt])==get(rt)?f[rt]:rt);}void access(int rt){int t=0;while(rt)Splay(rt),rs=t,PushUp(rt),t=rt,rt=f[rt];}void makeroot(int rt){access(rt),Splay(rt);swap(ls,rs);rev[rt]^=1;}int find(int rt){access(rt),Splay(rt);while(ls)PushDown(rt),rt=ls;Splay(rt);return rt;}void link(int rt,int x){makeroot(rt);f[rt]=x;}void cut(int rt,int x){makeroot(x);access(rt);Splay(rt);ls=f[x]=0;PushUp(rt);}void split(int rt,int x){makeroot(x);access(rt);Splay(rt);}bool cmp(const node &a,const node &b){return a.l==b.l?a.r
            
             
              >1)&1))flag=1; if(val[mx[x]]>=a[p].r)tmp=p; else tmp=mx[x]-n,cut(tmp+n,a[tmp].x),cut(tmp+n,a[tmp].y),link(p+n,x),link(p+n,y); if(flag&&a[tmp].r>now)num[a[tmp].r]++,sum++; } }}int main(){ n=rd(),Q=rd();int T=rd(); for(int i=1;i<=Q;i++)a[i].x=rd(),a[i].y=rd(),a[i].l=rd(),a[i].r=rd(); sort(a+1,a+Q+1,cmp); for(int i=1;i<=n+Q;i++)siz[i]=1,mx[i]=i; for(int i=0;i<=n;i++)val[i]=1<<30; for(int i=1;i<=Q;i++)val[i+n]=a[i].r; for(int i=0,j=1;i