题目背景
动态树
题目描述
给定N个点以及每个点的权值,要你处理接下来的M个操作。操作有4种。操作从0到3编号。点从1到N编号。
0:后接两个整数(x,y),代表询问从x到y的路径上的点的权值的xor和。保证x到y是联通的。
1:后接两个整数(x,y),代表连接x到y,若x到Y已经联通则无需连接。
2:后接两个整数(x,y),代表删除边(x,y),不保证边(x,y)存在。
3:后接两个整数(x,y),代表将点X上的权值变成Y。
输入输出格式
输入格式:
第1行两个整数,分别为N和M,代表点数和操作数。
第2行到第N+1行,每行一个整数,整数在[1,10^9]内,代表每个点的权值。
第N+2行到第N+M+1行,每行三个整数,分别代表操作类型和操作所需的量。
输出格式:
对于每一个0号操作,你须输出X到Y的路径上点权的Xor和。
输入输出样例
输入样例#1:
3 3 1 2 3 1 1 2 0 1 2 0 1 1
输出样例#1:
3 1
说明
1<=N,M<=300000
一颗维护区间值的LCT,值得注意的是pushup的位置和写法,pushdown和普通的LCT是一样的,另外,makeroot操作的时候要小心。
写的不是很好看的代码:
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn = 3e5+100; int n,m; namespace LCT { struct node { int ch[2], fa, sum, num; bool rv; }tree[maxn]; const int L=0, R=1; #define isroot(x) (tree[tree[x].fa].ch[L] != x && tree[tree[x].fa].ch[R] != x) void push_up(int rt) { tree[rt].sum = tree[rt].num; /* ^0 操作会对结果造成影响*/ if( tree[rt].ch[L] ) tree[rt].sum ^= tree[tree[rt].ch[L]].sum; if( tree[rt].ch[R] ) tree[rt].sum ^= tree[tree[rt].ch[R]].sum; } void push_down(int rt) { if( tree[rt].rv ) { tree[tree[rt].ch[L]].rv ^= 1; tree[tree[rt].ch[R]].rv ^= 1; swap(tree[rt].ch[L], tree[rt].ch[R]); tree[rt].rv = 0; } } void rotate(int rt) { int p = tree[rt].fa; int a = tree[p].fa; int v = tree[p].ch[R] == rt; if( !isroot(p) ) tree[a].ch[tree[a].ch[R] == p] = rt; tree[p].ch[v] = tree[rt].ch[v^1], tree[tree[p].ch[v]].fa = p; tree[rt].ch[v^1] = p, tree[p].fa = rt, tree[rt].fa = a; push_up(p), push_up(rt), push_up(a); /*有三个pushup!*/ } void splay(int rt, int y){ int des = tree[y].fa; while( tree[rt].fa != des ){ int p = tree[rt].fa, a = tree[p].fa; push_down(a), push_down(p), push_down(rt); if( p != y ) if( (tree[a].ch[R] == p) ^ (tree[p].ch[R] == rt) ) rotate(rt); else rotate(p); rotate(rt); } } int find_root(int now){ int u;for(u = now; !isroot(u); u = tree[u].fa); return u; } void change(int rt, int ch){ int u = find_root(rt); splay(rt, u), push_down(rt);/*记得pushdown 不要伏笔*/ tree[rt].ch[R] = ch; push_up(rt);/*更新之后还得pushup*/ } int access(int rt){ for(change(rt,0); tree[rt].fa; rt = tree[rt].fa) change(tree[rt].fa, rt); int u = rt; while( push_down(u), tree[u].ch[L] ) u = tree[u].ch[L]; return splay(u, rt), u; } /*makeroot操作,reverse的应该是树根不是x*/ #define makeroot(x) (tree[access(x)].rv ^= 1) #define link(a, b) (tree[b = access(b)].rv ^= 1, tree[b].fa = a) #define cut(a, b) (change(a, 0), change(b, 0), tree[a].fa == b ? tree[a].fa = 0 : tree[b].fa = 0) #define connect(a, b) (access(a) == access(b)) int qnode(int now, bool type){ now = tree[now].ch[type]; while( tree[now].ch[type^1] ) now = tree[now].ch[type^1]; return now; } /*普通的splay区间查询*/ int Splay_query(int a, int b){ int root = find_root(a); int org_a = a; a = qnode(a, 0); b = qnode(b, 1); if( !a && !b ) return tree[org_a].sum; if( !a ) {splay(b, root); return tree[tree[b].ch[L]].sum;} else if( !b ){splay(a, root); return tree[tree[a].ch[R]].sum;} else {splay(a, root), splay(b, tree[a].ch[R]); return tree[tree[b].ch[L]].sum;} } int query(int a, int b){ makeroot(a); access(b); return Splay_query(a, b); } } int main(){ using namespace LCT; scanf("%d%d", &n, &m); for(int i = 1; i <= n; i++) scanf("%d", &tree[i].num), tree[i].sum = tree[i].num; for(int i = 1; i <= m; i++){ int opt, a, b; scanf("%d%d%d", &opt, &a, &b); if(opt == 1) if(!connect(a,b)) link(a, b);/*记得判联通*/ if(opt == 0) printf("%d\n",query(a, b)); if(opt == 2) if(connect(a,b)) cut(a, b); if(opt == 3) tree[a].sum = tree[a].num = b, access(a), push_up(a); } return 0; }
没有帐号? 立即注册