1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
| #define void inline void const int maxn = 300000 + 5;
int n, m, a[maxn];
struct lct { int fa[maxn], ch[maxn][2], rev[maxn], s[maxn]; int nroot(int x) { return ch[fa[x]][0] == x || ch[fa[x]][1] == x; } int get(int x) { return ch[fa[x]][1] == x; } void pushup(int x) { s[x] = s[ch[x][0]] ^ s[ch[x][1]] ^ a[x]; } void pushrev(int x) { swap(ch[x][0], ch[x][1]); rev[x] ^= 1; } void pushdown(int x) { if (!rev[x]) return; if (ch[x][0]) pushrev(ch[x][0]); if (ch[x][1]) pushrev(ch[x][1]); rev[x] = 0; } void rot(int x) { int old = fa[x], oldf = fa[old], k = get(x), w = ch[x][k ^ 1]; if (nroot(old)) ch[oldf][ch[oldf][1] == old] = x; ch[x][k ^ 1] = old; ch[old][k] = w; if (w) fa[w] = old; fa[old] = x; fa[x] = oldf; pushup(old); } int st[maxn]; void splay(int x) { int y = x, t = 0; st[++t] = y; while (nroot(y)) st[++t] = fa[y], y = fa[y]; while (t) pushdown(st[t--]); while (nroot(x)) { y = fa[x]; if (nroot(y)) rot(get(x) == get(y) ? y : x); rot(x); } pushup(x); } void access(int x) { for (int y = 0; x; y = x, x = fa[x]) splay(x), ch[x][1] = y, pushup(x); } void make(int x) { access(x); splay(x); pushrev(x); } int findroot(int x) { access(x); splay(x); while (ch[x][0]) pushdown(x), x = ch[x][0]; return x; } void split(int x, int y) { make(x); access(y); splay(y); } int link(int x, int y) { make(x); if (findroot(y) == x) return 0; fa[x] = y; return 1; } int cut(int x, int y) { make(x); if (findroot(y) != x || fa[x] != y || ch[x][1]) return 0; fa[x] = ch[y][0] = 0; pushup(y); return 1; } int qpath(int l, int r) { split(l, r); return s[r]; } void upoint(int x, int y) { splay(x); a[x] = y; } } f;
|