1. 题目

传送门= ̄ω ̄=

2. 题解

把pushup改成求异或和就行了
代码:

#include <bits/stdc++.h>
#define NS (300005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
    char c=getchar();dig=0;int f=1;
    while(!isdigit(c)&&c!='-')c=getchar();
    if(c=='-')f=-1,c=getchar();
    while(isdigit(c))dig=dig*10+c-'0',c=getchar();
    dig*=f;
}
struct N{int f,s[2],rev,d,v;N(){f=s[0]=s[1]=rev=d=0;}}e[NS];
bool isroot(int a){return e[e[a].f].s[0]!=a&&e[e[a].f].s[1]!=a;}
void pup(int a){e[a].d=(e[e[a].s[0]].d^e[e[a].s[1]].d^e[a].v);}
void pdown(int a)
{
    if(!e[a].rev)return;
    e[a].rev=0,e[e[a].s[0]].rev^=1,e[e[a].s[1]].rev^=1;
    swap(e[a].s[0],e[a].s[1]);
}
bool pos(int a){return e[e[a].f].s[1]==a;}
void rot(int a)
{
    int f=e[a].f,g=e[f].f,p=pos(a);
    if(!isroot(f))e[g].s[pos(f)]=a;
    e[a].f=g,e[f].f=a,e[f].s[p]=e[a].s[!p],e[a].s[!p]=f;
    if(e[f].s[p])e[e[f].s[p]].f=f;
    pup(f),pup(a);
}
int st[NS],top;
void splay(int a)
{
    st[++top]=a;
    for(int i=a;!isroot(i);i=e[i].f)st[++top]=e[i].f;
    while(top)pdown(st[top--]);
    while(!isroot(a))
        if(isroot(e[a].f))rot(a);
        else if(pos(a)^pos(e[a].f))rot(a),rot(a);
        else rot(e[a].f),rot(a);
}
void acc(int a){int b=0;while(a)splay(a),e[a].s[1]=b,pup(a),b=a,a=e[a].f;}
void evert(int a){acc(a),splay(a),e[a].rev^=1;}
void split(int a,int b){evert(b),acc(a),splay(a);}
void link(int a,int b){evert(a),e[a].f=b;}
void cut(int a,int b){split(a,b);if(e[a].s[0]==b)e[a].s[0]=e[b].f=0;}
int find(int a){acc(a),splay(a);while(e[a].s[0])a=e[a].s[0];return a;}
int n,m;
int main()
{
    IN(n),IN(m);
    for(int i=1;i<=n;i++)IN(e[i].v),e[i].d=e[i].v;
    for(int i=1,a,b,c;i<=m;i++)
    {
        IN(a),IN(b),IN(c);
        if(a==0)split(b,c),printf("%d\n",e[b].d);
        else if(a==1){if(find(b)==find(c))continue;link(b,c);}
        else if(a==2){if(find(b)!=find(c))continue;cut(b,c);}
        else acc(b),splay(b),e[b].v=c;
    }
    return 0;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *