BZOJ 4025: 二分图

男娘i 2021-12-23 03:39 242阅读 0赞

## BZOJ 4025: 二分图 ##

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

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

#include <cstdio>
    #include <algorithm>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <queue>
    #include <iostream>
    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<b.r:a.l<b.l;}
    void add(int p)
    {
        int x=a[p].x,y=a[p].y,tmp,flag=0;
        if(x==y)num[a[p].r]++,sum++;
        else 
        {
            // printf("%d %d\n",find(x),find(y));
            if(find(x)!=find(y))link(p+n,x),link(y,p+n);
            else
            {
                split(x,y);
                if(!((siz[x]>>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<T;i++)
        {
            now=i;
            while(j<=Q&&a[j].l<=i)add(j),j++;
            sum-=num[i];
            if(sum)puts("No");
            else puts("Yes");
        }return 0;
    }

转载于:https://www.cnblogs.com/Winniechen/p/9525768.html