[luogu3767]膜法

luogu

神仙题

线段树分治+带权并查集

把每个操作看成点

首先这个操作的结构是一棵树

你发现每个点的对它的子树产生影响

我们可以想到用dfn序把它转成一段区间用线段树分治来做

但是还有删除操作,相当于在一个大区间里面挖掉几个小区间

可以对每个操作开一个vector记录区间搞一搞

然后带权并查集是模5意义下的,可以认为给你的操作相当于从u连向v的一条权值为1或2的边

当u,v在同一个集合时,判断是否满足条件,否则就连边

#define pb push_back

#define ls x<<1,l,mid

#define rs x<<1|1,mid+1,r

#include<bits/stdc++.h>

using namespace std;

const int _=1e5+5;

int re(){

    int x=0,w=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*w;

}

int n,m,ts,top,dis;

int fa[_],del[_],sz[_],dfn[_],par[_],siz[_],d[_];

bool ans[_];

struct node{int u,v;}st[_];

struct edge{int u,v,w;}e[_];

vector<int>son[_],s[_];

vector<edge>t[_<<2];

void dfs(int u){

    sz[u]=1;if(u)dfn[u]=++ts;

    if(del[u])s[del[u]].pb(u);

    for(int i=0,j=son[u].size();i<j;i++){

        int v=son[u][i];

        dfs(v);sz[u]+=sz[v];

    }

}

void add(int&x,int y){x=(x+y)%5;}

int find(int x){

    add(dis,d[x]);

    if(x==par[x])return x;

    return find(par[x]);

}

void upd(int x,int l,int r,int ql,int qr,edge E){

    if(ql<=l&&r<=qr){t[x].pb(E);return;}

    int mid=(l+r)>>1;if(ql<=mid)upd(ls,ql,qr,E);

    if(qr>mid)upd(rs,ql,qr,E);

}

void solve(int x,int l,int r,bool ok){

    int pre=top;

    for(int i=0,j=t[x].size();i<j;i++){

        int u=t[x][i].u,v=t[x][i].v,w=t[x][i].w;

        dis=0;int fu=find(u),du=dis;

        dis=0;int fv=find(v),dv=dis;

        if(fu==fv&&(du-dv+5)%5!=w)ok=0;

        if(fu^fv){

            if(siz[fu]>siz[fv]){swap(du,dv);swap(u,v);swap(fu,fv);w=-w;}

            siz[fv]+=siz[fu];par[fu]=fv;

            d[fu]=(w+dv-du+10)%5;st[++top]=(node){fu,fv};

        }

    }

    if(l==r)ans[l]=ok;

    else{int mid=(l+r)>>1;solve(ls,ok);solve(rs,ok);}

    while(top^pre){

        int u=st[top].u,v=st[top].v;top--;

        siz[v]-=siz[u];par[u]=u;d[u]=0;

    }

}

int main(){

    n=re(),m=re();

    int op,u,v;

    for(int i=1;i<=m;i++){

        son[fa[i]=re()].pb(i);op=re();

        if(op==3)del[i]=re();

        else{u=re(),v=re();e[i]=(edge){u,v,op};}

    }

    dfs(0);

    for(int i=1;i<=m;i++){

        if(del[i])continue;

        int k=s[i].size(),lst=dfn[i];

        for(int j=0;j<k;j++){

            int u=s[i][j];

            if(lst<dfn[u])upd(1,1,m,lst,dfn[u]-1,e[i]);

            lst=dfn[u]+sz[u];

        }

        if(lst<dfn[i]+sz[i])upd(1,1,m,lst,dfn[i]+sz[i]-1,e[i]);

    }

    for(int i=1;i<=n;i++)par[i]=i,siz[i]=1;

    solve(1,1,m,1);

    for(int i=1;i<=m;i++)puts(ans[dfn[i]]?"excited":"naive");

    return 0;

}

巴特西

[luogu3767]膜法

[luogu3767]膜法

最新文章

热门文章