CF-246E
题意简述
给定一片 n 个点的森林，每次询问一个节点的K-Son共有个多少不同的名字。一个节点的K-Son即为深度是该节点深度加 K 的节点。
n,q≤105
题解
首先看一个弱化版的题目：CF208E Blood Cousins ，题意是 给你一片森林，每次询问一个点与多少个点拥有共同的 K 级祖先。
把所有根结点连向 0 ，可以 Dfs 出 dfn 序，要求的便是一个点向下 K 层 dfn 序在该点范围内的点有多少个，双关键字（先深度后dfn序）排序后，每次询问二分答案即可。
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
| #include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void red(T &x) {
x=0;bool fg=0;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(T)(ch^48),ch=getchar();
if(fg) x=-x;
}
const int N = 100010;
const int M = 18;
int dL[N],dR[N],tim;
int head[N],pnt[N<<1],nxt[N<<1],E;
int n,q,dep[N],fa[N][M];
vector<int> dd[N];
void adde(int u,int v) {
E++;pnt[E]=v;nxt[E]=head[u];head[u]=E;
}
void dfs(int u) {
dL[u]=++tim;
dd[dep[u]].push_back(tim);
for(int i=1;i<M&&fa[u][i-1]!=-1;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u];i;i=nxt[i]) {
int v=pnt[i];
if(v==fa[u][0]) continue;
dep[v]=dep[u]+1;
dfs(v);
}
dR[u]=tim;
}
int jump(int v,int k) {
for(int i=0;i<M;i++) if((k>>i)&1) v=fa[v][i];
return v;
}
int main() {
red(n);
memset(fa,-1,sizeof(fa));
for(int i=1;i<=n;i++) {
red(fa[i][0]);
adde(fa[i][0],i);
}
dfs(0);
red(q);
while(q--) {
int v,p;red(v);red(p);
v=jump(v,p);
if(v<=0) {printf("0 ");continue;}
int ans=upper_bound(dd[dep[v]+p].begin(),dd[dep[v]+p].end(),dR[v])-lower_bound(dd[dep[v]+p].begin(),dd[dep[v]+p].end(),dL[v]);
printf("%d ",ans-1);
}
printf("\n");
}
|
然后，再看一道题：HH的项链，给一个颜色序列，每次询问一段区间有多少种不同颜色。询问数，序列长度 1e6。
显然可以离线做，将所有询问按照 l 降序排序，维护每个颜色 lst[i] 表示该颜色 在当前左端点右 出现最左边的位置，对于一个询问 [l,r] 查询 ∑i[lst[i]≤r] 即可，可以用树状数组维护。
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
| #include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void red(T &x) {
x=0;bool fg=0;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(T)(ch^48),ch=getchar();
if(fg) x=-x;
}
const int N = 1000010;
int a[N],n,q,lst[N],ans[N];
struct trearr {
int t[N];
void add(int x,int v) {for(;x<=n;x+=x&-x) t[x]+=v;}
int sum(int x) {int r=0;for(;x;x-=x&-x) r+=t[x];return r;}
}t;
struct que {
int l,r,id;
bool operator<(const que a)const {
return l>a.l;
}
}p[N];
int main() {
red(n);
for(int i=1;i<=n;i++) red(a[i]);
red(q);
for(int i=1;i<=q;i++) {red(p[i].l);red(p[i].r);p[i].id=i;}
sort(p+1,p+q+1);
for(int ts=1,j=n;ts<=q;ts++) {
while(j>=p[ts].l) {
if(lst[a[j]]!=0) {
t.add(lst[a[j]],-1);
}
lst[a[j]]=j;
t.add(j,1);
j--;
}
ans[p[ts].id]=t.sum(p[ts].r);
}
for(int i=1;i<=q;i++) {
printf("%d\n",ans[i]);
}
return 0;
}
|
然后回头看这道题，便是用T1的方法转化乘序列上的问题，就变成T2了。。。
CODE
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
78
79
80
81
82
83
84
85
| #include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
template<typename T>
inline void red(T &x) {
x=0;bool fg=0;char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') fg^=1;ch=getchar();}
while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(T)(ch^48),ch=getchar();
if(fg) x=-x;
}
const int N = 100010;
int dL[N],dR[N],tim;
int head[N],pnt[N<<1],nxt[N<<1],E;
int n,q,dep[N],fa[N];
int c[N],col[N],tot,lst[N],ans[N];
pii dd[N];
struct trearr {
int t[N];
void add(int x,int v) {for(;x<=n;x+=x&-x) t[x]+=v;}
int sum(int x) {int r=0;for(;x;x-=x&-x) r+=t[x];return r;}
}t;
struct que {
int l,r,id;
bool operator<(const que a)const {
return l>a.l;
}
}p[N];int totq;
map<string,int> id;
void adde(int u,int v) {
E++;pnt[E]=v;nxt[E]=head[u];head[u]=E;
}
void dfs(int u) {
dL[u]=++tim;
dd[tim-1]=pii(dep[u],tim);
c[tim]=col[u];
for(int i=head[u];i;i=nxt[i]) {
int v=pnt[i];
if(v==fa[u]) continue;
dep[v]=dep[u]+1;
dfs(v);
}
dR[u]=tim;
}
int main() {
red(n);
memset(fa,-1,sizeof(fa));
for(int i=1;i<=n;i++) {
string a;cin>>a;
red(fa[i]);
adde(fa[i],i);
if(id[a]==0) id[a]=++tot;
col[i]=id[a];
}
dfs(0);
sort(dd+1,dd+n+1);
red(q);
for(int ts=1;ts<=q;ts++) {
int v,k;red(v);red(k);
int l=lower_bound(dd+1,dd+n+1,pii(dep[v]+k,dL[v]))-dd;
int r=upper_bound(dd+1,dd+n+1,pii(dep[v]+k,dR[v]))-dd-1;
if(l>r||l>n) continue;
totq++;
p[totq].id=ts;p[totq].l=l;p[totq].r=r;
}
sort(p+1,p+totq+1);
for(int ts=1,j=n;ts<=totq;ts++) {
while(j>=p[ts].l) {
if(lst[c[dd[j].se]]!=0) {
t.add(lst[c[dd[j].se]],-1);
}
lst[c[dd[j].se]]=j;
t.add(j,1);
j--;
}
ans[p[ts].id]=t.sum(p[ts].r);
}
for(int i=1;i<=q;i++) {
printf("%d\n",ans[i]);
}
return 0;
}
|
