题目背景

动态树

题目描述

给定Ｎ个点以及每个点的权值，要你处理接下来的Ｍ个操作。操作有４种。操作从０到３编号。点从１到Ｎ编号。

０：后接两个整数（ｘ，ｙ），代表询问从ｘ到ｙ的路径上的点的权值的ｘｏｒ和。保证ｘ到ｙ是联通的。

１：后接两个整数（ｘ，ｙ），代表连接ｘ到ｙ，若ｘ到Ｙ已经联通则无需连接。

２：后接两个整数（ｘ，ｙ），代表删除边（ｘ，ｙ），不保证边（ｘ，ｙ）存在。

３：后接两个整数（ｘ，ｙ），代表将点Ｘ上的权值变成Ｙ。

输入输出格式

输入格式：

第１行两个整数，分别为Ｎ和Ｍ，代表点数和操作数。

第２行到第Ｎ＋１行，每行一个整数，整数在［１，１０＾９］内，代表每个点的权值。

第Ｎ＋２行到第Ｎ＋Ｍ＋１行，每行三个整数，分别代表操作类型和操作所需的量。

输出格式：

对于每一个０号操作，你须输出Ｘ到Ｙ的路径上点权的Ｘｏｒ和。

输入输出样例

输入样例#1：

输出样例#1：

3
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;
}

Rockdu's Blog