[COJ2201][KOJ0223][KOJ0250]花园
试题描述
小奇的花园有n个温室，标号为1到n，温室以及以及温室间的双向道路形成一棵树。
每个温室都种植着一种花，随着季节的变换，温室里的花的种类也在不断发生着变化。
小奇想知道从温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。
输入
第一行为两个整数n，q，表示温室的数目和操作的数目。
第二行有n个整数T1，T2…Tn其中Ti表示温室i中的花的种类。
接下来n-1行,每个两个整数x, y,表示温室x和y之间有一条双向道路。
接下来q行,表示q个操作,分别为以下两种形式之一:
• C x t 表示在温室x中的花的种类变为t。
• Q x y t 表示询问温室x走到温室y的路径中(包括两个端点),第t种花出现的次数。
为了体现在线操作,输入数据中的每个操作的参数都进行了加密。记最后一次询问的答案为anslast(一开始设anslast为0),下次读入中的x,y,t均需要异或上anslast以得到真实值，在C/C++中异或为ˆ运算符，在pascal中为xor运算符。
输出
输出q行，每行一个正整数表示该次询问答案。
输入示例
5 8 10 20 30 40 50 1 2 1 3 3 4 3 5 Q 2 5 10 C 2 21 Q 3 4 21 C 6 22 Q 1 7 28 C 5 20 Q 2 5 20 Q 2 0 9
输出示例
1 2 0 3 1
数据规模及约定
对于30%的数据,有n <= 1000, q <= 2000。
对于50%的数据,有n <= 10000, q <= 20000。
对于100%的数据,有n <= 100000, q <= 200000，0 <= T < 2^31。
题解
解法一：树链剖分套线段树套 treap。T 飞~~
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 100010
#define maxm 200010
#define maxnode 7600010
struct Node {
int v, r, siz;
Node() {}
Node(int _, int __): v(_), r(__) {}
} ns[maxnode];
int ToT, fa[maxnode], ch[2][maxnode], rec;
int getnode() {
if(rec) {
int tmp = rec; rec = 0;
fa[tmp] = ch[0][tmp] = ch[1][tmp] = 0;
return tmp;
}
return ++ToT;
}
void maintain(int o) {
if(!o) return ;
ns[o].siz = 1;
for(int i = 0; i < 2; i++) if(ch[i][o])
ns[o].siz += ns[ch[i][o]].siz;
return ;
}
void rotate(int u) {
int y = fa[u], z = fa[y], l = 0, r = 1;
if(z) ch[ch[1][z]==y][z] = u;
if(ch[1][y] == u) swap(l, r);
fa[u] = z; fa[y] = u; fa[ch[r][u]] = y;
ch[l][y] = ch[r][u]; ch[r][u] = y;
maintain(y); maintain(u);
return ;
}
void insert(int& o, int v) {
if(!o) {
ns[o = getnode()] = Node(v, rand());
return maintain(o);
}
bool d = v > ns[o].v;
insert(ch[d][o], v); fa[ch[d][o]] = o;
if(ns[ch[d][o]].r > ns[o].r) {
int t = ch[d][o];
rotate(t); o = t;
}
return maintain(o);
}
void del(int& o, int v) {
if(!o) return ;
if(ns[o].v == v) {
if(!ch[0][o] && !ch[1][o]) rec = o, o = 0;
else if(!ch[0][o]) {
int t = ch[1][o]; fa[t] = fa[o]; rec = o; o = t;
}
else if(!ch[1][o]) {
int t = ch[0][o]; fa[t] = fa[o]; rec = o; o = t;
}
else {
bool d = ns[ch[1][o]].r > ns[ch[0][o]].r;
int t = ch[d][o]; rotate(t); o = t;
del(ch[d^1][o], v);
}
}
else {
bool d = v > ns[o].v;
del(ch[d][o], v);
}
return maintain(o);
}
int findlow(int o, int v) {
if(!o) return 0;
int ls = ch[0][o] ? ns[ch[0][o]].siz : 0;
if(v > ns[o].v) return ls + 1 + findlow(ch[1][o], v);
return findlow(ch[0][o], v);
}
int findupp(int o, int v) {
if(!o) return 0;
int ls = ch[0][o] ? ns[ch[0][o]].siz : 0;
if(v >= ns[o].v) return ls + 1 + findupp(ch[1][o], v);
return findupp(ch[0][o], v);
}
int rt[maxn<<2], val[maxn];
void Add(int L, int R, int o, int x) {
insert(rt[o], val[x]);
if(L == R) return ;
int M = L + R >> 1, lc = o << 1, rc = lc | 1;
if(x <= M) return Add(L, M, lc, x);
return Add(M+1, R, rc, x);
}
void Upd(int L, int R, int o, int x, int v) {
del(rt[o], val[x]); insert(rt[o], v);
if(L == R) return ;
int M = L + R >> 1, lc = o << 1, rc = lc | 1;
if(x <= M) return Upd(L, M, lc, x, v);
return Upd(M+1, R, rc, x, v);
}
int Que(int L, int R, int o, int ql, int qr, int v) {
if(ql <= L && R <= qr) return findupp(rt[o], v) - findlow(rt[o], v);
int M = L + R >> 1, lc = o << 1, rc = lc | 1, ans = 0;
if(ql <= M) ans += Que(L, M, lc, ql, qr, v);
if(qr > M) ans += Que(M+1, R, rc, ql, qr, v);
return ans;
}
int n, m, head[maxn], next[maxm], to[maxm];
void AddEdge(int a, int b) {
to[++m] = b; next[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; next[m] = head[a]; head[a] = m;
return ;
}
int pa[maxn], son[maxn], dep[maxn], siz[maxn], top[maxn], W[maxn], ww;
void build(int u) {
siz[u] = 1;
for(int e = head[u]; e; e = next[e]) if(to[e] != pa[u]) {
pa[to[e]] = u;
dep[to[e]] = dep[u] + 1;
build(to[e]);
siz[u] += siz[to[e]];
if(!son[u] || siz[son[u]] < siz[to[e]]) son[u] = to[e];
}
return ;
}
void gett(int u, int tp) {
W[u] = ++ww; top[u] = tp;
if(son[u]) gett(son[u], tp);
for(int e = head[u]; e; e = next[e]) if(to[e] != pa[u] && to[e] != son[u])
gett(to[e], to[e]);
return ;
}
int query(int a, int b, int v) {
int f1 = top[a], f2 = top[b], ans = 0;
while(f1 != f2) {
if(dep[f1] < dep[f2]) swap(f1, f2), swap(a, b);
int tmp = Que(1, n, 1, W[f1], W[a], v);
ans += Que(1, n, 1, W[f1], W[a], v);
a = pa[f1]; f1 = top[a];
}
if(dep[a] < dep[b]) swap(a, b);
int tmp = Que(1, n, 1, W[b], W[a], v);
ans += Que(1, n, 1, W[b], W[a], v);
return ans;
}
int T[maxn];
int main() {
n = read(); int q = read();
for(int i = 1; i <= n; i++) T[i] = read();
for(int i = 1; i < n; i++) {
int a = read(), b = read();
AddEdge(a, b);
}
build(1); gett(1, 1);
for(int i = 1; i <= n; i++) val[W[i]] = T[i];
for(int i = 1; i <= n; i++) Add(1, n, 1, i);
int lst = 0;
while(q--) {
char tp[2];
scanf("%s", tp);
if(tp[0] == 'C') {
int x = read() ^ lst, t = read() ^ lst;
Upd(1, n, 1, W[x], t); val[W[x]] = t;
}
if(tp[0] == 'Q') {
int a = read() ^ lst, b = read() ^ lst, t = read() ^ lst;
lst = query(a, b, t);
printf("%d
", lst);
}
}
return 0;
}
解法二：对于每一种颜色建一颗线段树，求一边 dfs 序把点修改链上询问转化成区间修改点询问的问题，线段树动态开节点防止爆炸。（别用 map 用 hash……）
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <cstring>
#include <string>
#include <map>
#include <set>
using namespace std;
int read() {
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
return x * f;
}
#define maxn 100010
#define maxm 200010
#define maxnode 10000010
int n, m, head[maxn], next[maxm], to[maxm], T[maxn];
#define MOD 233333
int Th, hd[MOD], nxt[maxn*3], Val[maxn*3];
int Find(int x) {
int v = (x % MOD + MOD) % MOD;
for(int e = hd[v]; e; e = nxt[e]) if(Val[e] == x) return e;
return 0;
}
void insert(int x) {
int v = (x % MOD + MOD) % MOD;
Val[++Th] = x; nxt[Th] = hd[v]; hd[v] = Th;
return ;
}
void AddEdge(int a, int b) {
to[++m] = b; next[m] = head[a]; head[a] = m;
swap(a, b);
to[++m] = b; next[m] = head[a]; head[a] = m;
return ;
}
int fa[maxn], son[maxn], siz[maxn], dep[maxn], top[maxn], W[maxn], ww, dl[maxn], dr[maxn];
void build(int u) {
siz[u] = 1;
for(int e = head[u]; e; e = next[e]) if(to[e] != fa[u]) {
fa[to[e]] = u;
dep[to[e]] = dep[u] + 1;
build(to[e]);
siz[u] += siz[to[e]];
if(!son[u] || siz[son[u]] < siz[to[e]]) son[u] = to[e];
}
return ;
}
void gett(int u, int tp) {
dl[u] = W[u] = ++ww; top[u] = tp;
if(son[u]) gett(son[u], tp);
for(int e = head[u]; e; e = next[e]) if(to[e] != fa[u] && to[e] != son[u])
gett(to[e], to[e]);
dr[u] = ww;
return ;
}
int lca(int a, int b) {
int f1 = top[a], f2 = top[b];
while(f1 != f2) {
if(dep[f1] < dep[f2]) swap(f1, f2), swap(a, b);
a = fa[f1]; f1 = top[a];
}
return dep[a] < dep[b] ? a : b;
}
int ToT, rt[maxn*3], lc[maxnode], rc[maxnode], S[maxnode], addv[maxnode];
void pushdown(int o, int L, int R) {
if(!addv[o]) return ;
S[o] += addv[o];
if(L < R) {
if(!lc[o]) lc[o] = ++ToT;
if(!rc[o]) rc[o] = ++ToT;
addv[lc[o]] += addv[o];
addv[rc[o]] += addv[o];
}
addv[o] = 0;
return ;
}
void update(int& o, int L, int R, int ql, int qr, int v) {
if(!o) o = ++ToT;
pushdown(o, L, R);
if(ql <= L && R <= qr) addv[o] += v;
else {
int M = L + R >> 1;
if(ql <= M) update(lc[o], L, M, ql, qr, v);
if(qr > M) update(rc[o], M+1, R, ql, qr, v);
}
return ;
}
int query(int o, int L, int R, int x) {
if(!x || !o) return 0;
pushdown(o, L, R);
if(L == R) return S[o];
int M = L + R >> 1;
if(x <= M) return query(lc[o], L, M, x);
return query(rc[o], M+1, R, x);
}
int main() {
n = read(); int q = read();
for(int i = 1; i <= n; i++) {
T[i] = read();
if(!Find(T[i])) insert(T[i]);
}
// for(int i = 1; i <= n; i++) printf("%d%c", Find(T[i]), i < n ? ' ' : '
');
for(int i = 1; i < n; i++) {
int a = read(), b = read();
AddEdge(a, b);
}
build(1); gett(1, 1);
// for(int i = 1; i <= n; i++) printf("%d: %d %d
", i, dl[i], dr[i]);
for(int i = 1; i <= n; i++) update(rt[Find(T[i])], 1, n, dl[i], dr[i], 1);
int lst = 0;
while(q--) {
char Tp[2]; scanf("%s", Tp);
if(Tp[0] == 'C') {
int x = read() ^ lst, t = read() ^ lst;
update(rt[Find(T[x])], 1, n, dl[x], dr[x], -1);
T[x] = t; if(!Find(t)) insert(t);
update(rt[Find(t)], 1, n, dl[x], dr[x], 1);
}
if(Tp[0] == 'Q') {
int a = read() ^ lst, b = read() ^ lst, t = rt[Find(read()^lst)], c = lca(a, b);
int A = query(t, 1, n, W[a]), B = query(t, 1, n, W[b]), C = query(t, 1, n, W[c]), fC = query(t, 1, n, W[fa[c]]);
// printf("%d %d %d(%d) %d(%d)
", A, B, C, c, fC, fa[c]);
lst = A + B - C - fC;
printf("%d
", lst);
}
}
return 0;
}