洛谷 P3690 【模板】Link Cut Tree
? 解题记录 ? ? 洛谷 ? ? LCT ? ? 模板 ?    2017-07-27 09:50:29    385    0    0

题目背景

动态树

题目描述

给定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;
}

 

上一篇: 洛谷 P1339 [USACO09OCT]热浪Heat Wave

下一篇: 洛谷P1525 关押罪犯

385 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航