题目背景
动态树
题目描述
给定 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 \leq N, M \leq 3 \cdot {10}^5\)
题解
看了那么久的博客, 终于开始打 LCT 了, 只不过现在还没有完全懂啊, 模板几乎照抄, 这种东西就背去吧
既然是模板题, 就没什么好说的了, LCT 维护就是链上的异或和, 其它的就完全是基本操作
- (如果你不知道 LCT 是什么或者没有学过 / 想学 LCT, 推荐一处 LCT 总结 + 题单 + 洛谷 P3690[模板]Link Cut Tree(动态树)(LCT,Splay) http://www.cnblogs.com/flashhu/p/8324551.html)
- #include <bits / stdc++.h> #define ll long long#define db double#define ld long double#define lc(x) ch[x][0]#define rc(x) ch[x][1] const int MAXN = 300000 + 10;
- int n,
- m,
- A[MAXN];
- struct LCT {
- int fa[MAXN],
- ch[MAXN][2],
- sum[MAXN],
- rev[MAXN];
- inline void init() {
- memset(fa, 0, sizeof(fa));
- memset(ch, 0, sizeof(ch));
- memset(sum, 0, sizeof(sum));
- memset(rev, 0, sizeof(rev));
- }
- inline bool nroot(int x) {
- return lc(fa[x]) == x || rc(fa[x]) == x;
- }
- inline void reverse(int x) {
- std: :swap(lc(x), rc(x));
- rev[x] ^= 1;
- }
- inline void pushup(int x) {
- sum[x] = sum[lc(x)] ^ sum[rc(x)] ^ A[x];
- }
- inline void pushdown(int x) {
- if (rev[x]) {
- if (lc(x)) reverse(lc(x));
- if (rc(x)) reverse(rc(x));
- rev[x] = 0;
- }
- }
- inline void rotate(int x) {
- int f = fa[x],
- p = fa[f],
- c = (rc(f) == x);
- if (nroot(f)) ch[p][ch[p][1] == f] = x;
- fa[ch[f][c] = ch[x][c ^ 1]] = f;
- fa[ch[x][c ^ 1] = f] = x;
- fa[x] = p;
- pushup(f);
- pushup(x);
- }
- inline void splay(int x) {
- std: :stack <int> s;
- s.push(x);
- for (register int i = x; nroot(i); i = fa[i]) s.push(fa[i]);
- while (!s.empty()) pushdown(s.top()),
- s.pop();
- for (register int y = fa[x]; nroot(x); rotate(x), y = fa[x]) if (nroot(y)) rotate((x == lc(y)) == (y == lc(fa[y])) ? y: x);
- pushup(x);
- }
- inline void access(int x) {
- for (register int y = 0; x; x = fa[y = x]) splay(x),
- rc(x) = y,
- pushup(x);
- }
- inline void makeroot(int x) {
- access(x);
- splay(x);
- reverse(x);
- }
- inline int findroot(int x) {
- access(x);
- splay(x);
- while (lc(x)) pushdown(x),
- x = lc(x);
- return x;
- }
- inline void split(int x, int y) {
- makeroot(x);
- access(y);
- splay(y);
- }
- inline void link(int x, int y) {
- makeroot(x);
- if (findroot(y) != x) fa[x] = y;
- }
- inline void cut(int x, int y) {
- makeroot(x);
- if (findroot(y) == x && fa[x] == y && !rc(x)) fa[x] = lc(y) = 0,
- pushup(y);
- }
- };
- LCT T;
- template <typename T> inline void read(T & x) {
- T data = 0,
- w = 1;
- char ch = 0;
- while (ch != '-' && (ch <'0' || ch> '9')) ch = getchar();
- if (ch == '-') w = -1,
- ch = getchar();
- while (ch>= '0' && ch <= '9') data = ((T) data <<3) + ((T) data << 1) + (ch ^ '0'),
- ch = getchar();
- x = data * w;
- }
- template < typename T> inline void write(T x, char c = '\0') {
- if (x <0) putchar('-'),
- x = -x;
- if (x> 9) write(x / 10);
- putchar(x % 10 + '0');
- if (c != '\0') putchar(c);
- }
- template <typename T> inline void chkmin(T & x, T y) {
- x = (y <x ? y: x);
- }
- template < typename T> inline void chkmax(T & x, T y) {
- x = (y> x ? y: x);
- }
- template <typename T> inline T min(T x, T y) {
- return x <y ? x: y;
- }
- template < typename T> inline T max(T x, T y) {
- return x> y ? x: y;
- }
- int main() {
- read(n);
- read(m);
- for (register int i = 1; i <= n; ++i) read(A[i]);
- T.init();
- while (m--) {
- int opt,
- x,
- y;
- read(opt);
- read(x);
- read(y);
- if (opt == 0) T.split(x, y),
- write(T.sum[y], '\n');
- if (opt == 1) T.link(x, y);
- if (opt == 2) T.cut(x, y);
- if (opt == 3) T.splay(x),
- A[x] = y;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2544867.html