相关链接
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4771
数据生成器：http://paste.ubuntu.com/24181811/
神犇题解：https://blog.sengxian.com/solutions/bzoj-4771
解题报告
这题sengxian又写了题解了，我又不想写了…..
不过，还是XJB说一说吧！题还是很好的
就是搞两类线段树，两类线段树都支持合并
其中一类线段树，下标是颜色的编号，叶子结点记录的是该种颜色的最浅深度，这个是用来更新第二类线段树的
另一类线段树的下标是深度，结点记录的是区间和，这个是用来回答询问的
我们先把第二类线段树给Merge起来，不过我们发现同一种颜色可能会算重
不过我们也可以发现，再Merge第一类线段树的时候，如果叶子结点重了
那么在第一类线段树里减掉深度较深的那个点之后，答案就没有问题了
另外的话，因为这题强制在线
于是我们还需要把第一类线段树给可持久化
总的时间复杂度：$O(n \log n)$
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 200009;
const int M = 1e7;
int n,m,head[N],to[N],nxt[N],dep[N],col[N],fa[N];
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
class Segment_Tree_Sum{
int cnt,AnsTmp,root[N],ch[M][2],sum[M];
public:
inline void modify(int w, int p, int delta) {
modify(root[w], 1, n, p, delta);
}
inline void merge(int a, int b) {
root[a] = Merge(root[a], root[b]);
}
inline int query(int w, int d) {
AnsTmp = 0;
query(root[w], 1, n, 1, d);
return AnsTmp;
}
inline void init() {
memset(root,0,sizeof(int)*(n+5));
memset(ch,0,sizeof(int)*(cnt+5)*2);
memset(sum,0,sizeof(int)*(cnt+5));
cnt = 0;
}
private:
void modify(int &w, int l, int r, int p, int delta) {
w = cpy(w); sum[w] += delta;
if (l < r) {
int mid = l + r + 1 >> 1;
if (p < mid) modify(ch[w][0], l, mid-1, p, delta);
else modify(ch[w][1], mid, r, p, delta);
}
}
int Merge(int a, int b) {
a = a? cpy(a): 0; b = b? cpy(b): 0;
if (!b || !a) return a + b;
else {
if (ch[a][0] || ch[a][1]) {
ch[a][0] = Merge(ch[a][0], ch[b][0]);
ch[a][1] = Merge(ch[a][1], ch[b][1]);
}
return sum[a] += sum[b], a;
}
}
void query(int w, int l, int r, int L, int R) {
if (L <= l && r <= R) AnsTmp += sum[w];
else {
int mid = l + r + 1 >> 1;
if (L < mid) query(ch[w][0], l, mid-1, L, R);
if (mid <= R) query(ch[w][1], mid, r, L, R);
}
}
inline int cpy(int b) {
memcpy(ch[++cnt], ch[b], 8);
sum[cnt] = sum[b]; return cnt;
}
}STS;
class Segment_Tree_Col{
int cnt,root[N],ch[M][2],mn[M];
public:
inline void insert(int w, int c) {
insert(root[w], 1, n, c, dep[w]);
STS.modify(w, dep[w], 1);
}
inline void merge(int a, int b) {
STS.merge(a, b);
root[a] = merge(root[a], root[b], a);
}
inline void init() {
memset(root,0,sizeof(int)*(n+5));
memset(ch,0,sizeof(int)*(cnt+5)*2);
memset(mn,0,sizeof(int)*(cnt+5));
cnt = 0;
}
private:
void insert(int &w, int l, int r, int p, int v) {
if (!w) w = ++cnt; if (l == r) mn[w] = v;
else {
int mid = l + r + 1 >> 1;
if (p < mid) insert(ch[w][0], l, mid-1, p, v);
else insert(ch[w][1], mid, r, p, v);
}
}
int merge(int a, int b, int w) {
if (!a || !b) return a + b;
else if (ch[a][0] || ch[a][1]) {
ch[a][0] = merge(ch[a][0], ch[b][0], w);
ch[a][1] = merge(ch[a][1], ch[b][1], w);
} else {
STS.modify(w, max(mn[a], mn[b]), -1);
mn[a] = min(mn[a], mn[b]);
} return a;
}
}STC;
int main() {
for (int T=read();T;T--) {
n = read(); m = read();
STS.init(); STC.init(); dep[1] = 1;
for (int i=1;i<=n;i++) col[i] = read();
for (int i=2;i<=n;i++) dep[i] = dep[fa[i]=read()] + 1;
for (int i=1;i<=n;i++) STC.insert(i, col[i]);
for (int i=n;i>1;i--) STC.merge(fa[i], i);
for (int i=1,x,d,last=0;i<=m;i++) {
x = read() ^ last; d = read() ^ last;
printf("%d\n",last=STS.query(x, dep[x]+d));
}
}
return 0;
}
—————————— UPD 2017.4.11 ——————————
似乎Clairs之前出过这个题了…….
http://www.cnblogs.com/clrs97/p/5538804.html
