【bzoj3282、2631、2002、2049】

2015.03.22 17:48 Sun | 15次阅读 | 旧日oi | 固定链接 | 源码

link cut tree四连击!!!!
2049无向图,2002有向图,纯模版
2631比较恶心,双标记下传,果断去看了一眼1798……中途wa了好多次,没想到竟然是初始化的问题……泪奔……
做完了2631再看3282就比较水了,把2049的代码随便加点pushup,再加两个不超过3行的操作函数就好了,1A之
这种数据结构的东西不写挂就好了,常数什么的以后再说……

我的程序

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 300010
#define isroot(x) (son[fa[x]][0]!=x&&son[fa[x]][1]!=x)
#define is(x) son[fa[x]][1]==x
#define ls son[x][0]
#define rs son[x][1]
using namespace std;
struct LCT{
    int cnt,tmp;
    int fa[maxn],son[maxn][2],val[maxn],sum[maxn];bool flag[maxn];
    int st[maxn],top;
    int newnode()
    {
        cnt++;scanf("%d",&tmp);val[cnt]=sum[cnt]=tmp;
        son[cnt][0]=son[cnt][1]=fa[cnt]=0;
        return cnt;
    }
    void pushup(int x)
    {
        sum[x]=sum[ls]^sum[rs]^val[x];
    }
    void reverse(int x)
    {
        flag[x]^=1;
        swap(ls,rs);
    }
    void pushdown(int x)
    {
        if(flag[x])
        {
            reverse(x);
            flag[ls]^=1;flag[rs]^=1;
            flag[0]=0;
        }
    }
    void pushpath(int x)
    {
        for(top=0;!isroot(x);x=fa[x]) st[++top]=x;
        st[++top]=x;
        while(top) pushdown(st[top--]);
    }
    void link(int x,int y,int d){
        son[y][d]=x;fa[x]=y;
    }
    void rotate(int x)
    {
        int y=fa[x],z=fa[y],id=is(x),t=son[x][!id];
        if(!isroot(y)) link(x,z,is(y));
        else fa[x]=z;link(t,y,id);link(y,x,!id);
        fa[0]=son[0][0]=son[0][1]=0;
        pushup(y);
    }
    void splay(int x)
    {
        int y,z;
        pushpath(x);
        while(!isroot(x))
        {
            y=fa[x];z=fa[y];
            if(isroot(y)) {
                rotate(x);break;
            }
            rotate(is(x)==is(y)?y:x);rotate(x);
        }
        pushup(x);
    }
    void access(int x)
    {
        int p=0;
        while(x)
        {
            splay(x);
            rs=p;pushup(x);
            p=x;x=fa[x];
        }
    }
    void makeroot(int x)
    {
        access(x);
        splay(x);
        flag[x]=1;
        pushdown(x);
    }
    void connect(int x,int y)
    {
        makeroot(x);
        fa[x]=y;
    }
    void cut(int x,int y)
    {
        makeroot(y);
        access(x);
        splay(x);
        if(ls==y) ls=fa[y]=0;
    }
    int query(int x,int y)
    {
        makeroot(y);
        access(x);splay(x);
        return sum[x];
    }
    void change(int x,int y)
    {
        makeroot(x);
        val[x]=y;
        pushup(x);
    }
    int findroot(int x)
    {
        while(fa[x]) x=fa[x];
        return x;
    }
}lct;
int n,m,u,v,opt;
int pos[maxn];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) pos[i]=lct.newnode();
    while(m--)
    {
        scanf("%d%d%d",&opt,&u,&v);
        if(opt==0) printf("%d\n",lct.query(pos[u],pos[v]));
        else if(opt==1) {
            if(lct.findroot(pos[u])!=lct.findroot(pos[v])) lct.connect(pos[u],pos[v]);
        }
        else if(opt==2) lct.cut(pos[u],pos[v]);
        else lct.change(pos[u],v);
    }
    return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 100100
#define mod 51061
#define ls son[x][0]
#define rs son[x][1]
#define is(x) son[fa[x]][1]==x
#define isroot(x) (son[fa[x]][0]!=x&&son[fa[x]][1]!=x)
#define ll unsigned int
using namespace std;
struct LCT{
    int siz[maxn],fa[maxn],son[maxn][2],cnt;
    bool re[maxn];ll ad[maxn],mu[maxn],sum[maxn],val[maxn];
    int st[maxn],top;
    int newnode()
    {
        siz[++cnt]=val[cnt]=sum[cnt]=1;
        fa[cnt]=son[cnt][0]=son[cnt][1]=0;
        re[cnt]=ad[cnt]=0;mu[cnt]=1;
        return cnt;
    }
    void pushup(int x)
    {
        if(x==0) return;
        siz[x]=siz[ls]+siz[rs]+1;
        sum[x]=(sum[ls]+sum[rs]+val[x])%mod;
    }
    void reverse(int x){
        if(!x) return;
        re[x]^=1;
        swap(ls,rs);
    }
    void add(int x,ll c){
        if(!x) return;
        val[x]+=c;val[x]%=mod;
        ad[x]+=c;ad[x]%=mod;
        sum[x]+=c*siz[x];sum[x]%=mod;
    }
    void times(int x,ll c)
    {
        if(!x) return;
        val[x]*=c;val[x]%=mod;
        ad[x]*=c;ad[x]%=mod;
        mu[x]*=c;mu[x]%=mod;
        sum[x]*=c;sum[x]%=mod;
    }
    void pushdown(int x)
    {
        if(x==0) return;
        if(mu[x]^1)
        {
            times(ls,mu[x]);
            times(rs,mu[x]);
            mu[x]=1;
        }
        if(ad[x])
        {
            add(ls,ad[x]);
            add(rs,ad[x]);
            ad[x]=0;
        }
        if(re[x])
        {
            reverse(ls);
            reverse(rs);
            re[x]=0;
        }
    }
    void pushpath(int x)
    {
        for(top=0;!isroot(x);x=fa[x]) st[++top]=x;
        st[++top]=x;
        while(top) pushdown(st[top--]);
    }
    void connect(int x,int y,int d){
        son[y][d]=x;fa[x]=y;
    }
    void rotate(int x){
        int y=fa[x],z=fa[y],id=is(x),t=son[x][!id];
        if(!isroot(y)) connect(x,z,is(y));
        else fa[x]=z;
        connect(t,y,id);connect(y,x,!id);
        pushup(y);
    }
    void splay(int x)
    {
        pushpath(x);
        int y,z;
        while(!isroot(x))
        {
            y=fa[x];z=fa[y];
            if(isroot(y)) {
                rotate(x);
                break;
            }
            rotate(is(y)==is(x)?y:x);rotate(x);
        }
        pushup(x);
    }
    void access(int x)
    {
        int p=0;
        while(x)
        {
            splay(x);
            rs=p;
            pushup(x);
            p=x;x=fa[x];
        }
    }
    void movetoroot(int x)
    {
        access(x);
        splay(x);
        reverse(x);
    }
    void link(int x,int y)
    {
        movetoroot(x);
        fa[x]=y;
    }
    void cut(int x,int y)
    {
        movetoroot(y);
        access(x);
        splay(x);
        ls=0;fa[y]=0;pushup(x);
    }
    void addd(int x,int y,ll c)
    {
        movetoroot(y);
        access(x);splay(x);
        add(x,c);
    }
    void multi(int x,int y,ll c)
    {
        movetoroot(y);
        access(x);splay(x);
        times(x,c);
    }
    int query(int x,int y)
    {
        movetoroot(y);
        access(x);splay(x);
        return sum[x]%mod;
    }
}lct;
int n,q,u,v,x,y,c;
char s[2];
int pos[maxn];
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) pos[i]=lct.newnode();
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);
        lct.link(pos[u],pos[v]);
    }
    while(q--)
    {
        scanf("%s%d%d",s,&u,&v);
        if(s[0]=='+'){
            scanf("%lld",&c);
            lct.addd(pos[u],pos[v],c);
        }
        else if(s[0]=='-'){
            scanf("%d%d",&x,&y);
            lct.cut(pos[u],pos[v]);
            lct.link(pos[x],pos[y]);
        }
        else if(s[0]=='*'){
            scanf("%lld",&c);
            lct.multi(pos[u],pos[v],c);
        }
        else printf("%d\n",lct.query(pos[u],pos[v]));
    }
    return 0;
}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 200010
#define isroot(x) (son[fa[x]][0]!=x&&son[fa[x]][1]!=x)
#define is(x) son[fa[x]][1]==x
#define ls son[x][0]
#define rs son[x][1]
using namespace std;
struct LCT{
    int cnt;
    int fa[maxn],son[maxn][2],siz[maxn];//bool flag[maxn];
    int st[maxn],top;
    int newnode()
    {
        siz[++cnt]=1;
        son[cnt][0]=son[cnt][1]=fa[cnt]=0;
        return cnt;
    }
    void update(int x)
    {
        siz[x]=siz[ls]+siz[rs]+1;
    }
    /*void reverse(int x)
    {
        flag[x]^=1;
        swap(ls,rs);
    }
    void pushdown(int x)
    {
        if(flag[x])
        {
            reverse(x);
            flag[ls]^=1;flag[rs]^=1;
            flag[0]=0;
        }
    }
    void pushpath(int x)
    {
        for(top=0;!isroot(x);x=fa[x]) st[++top]=x;
        st[++top]=x;
        while(top) pushdown(st[top--]);
    }*/
    void link(int x,int y,int d){
        son[y][d]=x;fa[x]=y;
    }
    void rotate(int x)
    {
        int y=fa[x],z=fa[y],id=is(x),t=son[x][!id];
        if(!isroot(y)) link(x,z,is(y));
        else fa[x]=z;link(t,y,id);link(y,x,!id);
        fa[0]=son[0][0]=son[0][1]=siz[0]=0;
        update(y);update(x);
    }
    void splay(int x)
    {
        int y,z;
        //pushpath(x);
        while(!isroot(x))
        {
            y=fa[x];z=fa[y];
            if(isroot(y)) {
                rotate(x);break;
            }
            rotate(is(x)==is(y)?y:x);rotate(x);
        }
    }
    void access(int x)
    {
        int p=0;
        while(x)
        {
            splay(x);
            rs=p;update(x);
            p=x;x=fa[x];
        }
    }
    void makeroot(int x)
    {
        access(x);
        splay(x);
        //flag[x]=1;
        //pushdown(x);
    }
    void connect(int x,int y)
    {
        makeroot(x);
        fa[ls]=0;ls=0;
        fa[x]=y;update(x);
    }
    /*void cut(int x,int y)
    {
        makeroot(y);
        access(x);
        splay(x);
        ls=fa[y]=0;
    }
    int findroot(int x)
    {
        int ret=0;
        while(fa[x]) x=fa[x],ret++;
        return ret;
    }*/
}lct;
int n,m,u,v,p;
int pos[maxn];
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) pos[i]=lct.newnode();
    for(int t,i=1;i<=n;i++) 
    {
        scanf("%d",&t);
        if(t+i<=n) lct.fa[pos[i]]=pos[t+i];
    }
    cin>>m;
    while(m--)
    {
        scanf("%d%d",&p,&u); u++;
        if(p==2) {
            scanf("%d",&v);
            if(u+v>n) lct.connect(pos[u],0);
            else lct.connect(pos[u],pos[u+v]);
        }
        else {
            lct.makeroot(pos[u]);
            printf("%d\n",lct.siz[lct.son[pos[u]][0]]+1);
        }
    }
    return 0;
}
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 10010
#define isroot(x) (son[fa[x]][0]!=x&&son[fa[x]][1]!=x)
#define is(x) son[fa[x]][1]==x
#define ls son[x][0]
#define rs son[x][1]
using namespace std;
struct LCT{
    int cnt;
    int fa[maxn],son[maxn][2];bool flag[maxn];
    int st[maxn],top;
    int newnode()
    {
        cnt++;
        son[cnt][0]=son[cnt][1]=fa[cnt]=0;
        return cnt;
    }
    void reverse(int x)
    {
        flag[x]^=1;
        swap(ls,rs);
    }
    void pushdown(int x)
    {
        if(flag[x])
        {
            reverse(x);
            flag[ls]^=1;flag[rs]^=1;
            flag[0]=0;
        }
    }
    void pushpath(int x)
    {
        for(top=0;!isroot(x);x=fa[x]) st[++top]=x;
        st[++top]=x;
        while(top) pushdown(st[top--]);
    }
    void link(int x,int y,int d){
        son[y][d]=x;fa[x]=y;
    }
    void rotate(int x)
    {
        int y=fa[x],z=fa[y],id=is(x),t=son[x][!id];
        if(!isroot(y)) link(x,z,is(y));
        else fa[x]=z;link(t,y,id);link(y,x,!id);
        fa[0]=son[0][0]=son[0][1]=0;
    }
    void splay(int x)
    {
        int y,z;
        pushpath(x);
        while(!isroot(x))
        {
            y=fa[x];z=fa[y];
            if(isroot(y)) {
                rotate(x);break;
            }
            rotate(is(x)==is(y)?y:x);rotate(x);
        }
    }
    void access(int x)
    {
        int p=0;
        while(x)
        {
            splay(x);
            rs=p;p=x;x=fa[x];
        }
    }
    void makeroot(int x)
    {
        access(x);
        splay(x);
        flag[x]=1;
        pushdown(x);
    }
    void connect(int x,int y)
    {
        makeroot(x);
        fa[x]=y;
    }
    void cut(int x,int y)
    {
        makeroot(y);
        access(x);
        splay(x);
        ls=fa[y]=0;
    }
    int findroot(int x)
    {
        while(fa[x]) x=fa[x];
        return x;
    }
}lct;
int n,m,u,v;
char s[10];
int pos[maxn];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) pos[i]=lct.newnode();
    while(m--)
    {
        scanf("%s%d%d",s,&u,&v);
        if(s[0]=='C') lct.connect(pos[u],pos[v]);
        else if(s[0]=='D') lct.cut(pos[u],pos[v]);
        else {
            if(lct.findroot(pos[u])==lct.findroot(pos[v])) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}```