51NOD1525 重组公司

  • Post author:
  • Post category:其他


这SB题我居然会WA?

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n,q;
char c;
inline void read(int&a)
{a=0;do c=getchar();while(c<'0'||c>'9');while(c<='9'&&c>='0')a=(a<<3)+(a<<1)+c-'0',c=getchar();}
struct Node
{
    int l,r;
    int flag;   
}T[2000001];

int f[200001];
int find(int x){return f[x]==x?f[x]:f[x]=find(f[x]);}


inline void up(int place)
{
    if(T[place<<1].flag&&T[place<<1|1].flag)
        if(find(T[place<<1].flag)==find(T[place<<1|1].flag))
        T[place].flag=f[T[place<<1].flag];
}

inline void Union(int place,int ne)
{
    if(!ne)return;
    if(!T[place].flag)T[place].flag=ne;
    if(find(T[place].flag)^find(ne))
        f[f[T[place].flag]]=f[ne];
}

void Build(int place,int l,int r)
{
    T[place].l=l,T[place].r=r,T[place].flag=0;
    if(l^r)
    Build(place<<1,l,l+r>>1),Build(place<<1|1,(l+r>>1)+1,r);
    else T[place].flag=l;
}

void Push(int place)
{
    Union(place<<1,T[place].flag);
    Union(place<<1|1,T[place].flag);
    T[place].flag=0;
}

void Cg(int place,int l,int r,int d)
{
    if(T[place].flag||T[place].l>=l&&T[place].r<=r)
    {
        if(!T[place].flag)
            for(int i=l;i<=r;i++)
                f[find(i)]=d;
        return Union(place,d);
    }   
    int Mid=T[place<<1].r;
    if(l<=Mid)Cg(place<<1,l,r,d);
    if(r>Mid)Cg(place<<1|1,l,r,d);
    up(place);
}

void Vis(int place,int l)
{
    if(T[place].l==T[place].r)return ;
    int Mid=T[place<<1].r;
    if(l<=Mid)Vis(place<<1,l);
    else Vis(place<<1|1,l);
}


int main()
{
    int n,m;
    read(n),read(m);
    Build(1,1,n);
    for(int i=1;i<=n;i++)f[i]=i;
    for(int i=1;i<=m;i++)
    {
        int op,x,y;
        read(op),read(x),read(y);
        if(op==1)
            Cg(1,x,x,find(y));
        else if(op==2)
            if(x^y)
            Cg(1,x,y-1,find(y));
            else;
        else
            puts(find(x)==find(y)?"YES":"NO");
    }
    return 0;
}



版权声明:本文为liutian429073576原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。