[阈值] BZOJ3351 [ioi2009]Regions

考虑这题时间复杂度的瓶颈在于,每种颜色对应一堆点。容易想到对颜色出现次数阈值。

若一种颜色出现次数小于 \(\sqrt n\) ,则说明对应点数较少。

若出现次数大于 \(\sqrt n\) ,则这样的颜色种数不会超过 \(\sqrt n\) 种。

这样就能做了,对询问 \((r1,r2)\) ,若 \(cnt_{r2} \le \sqrt n\) ,把询问挂在 \(r2\) 上,这样最多挂 \(Q\sqrt n\) 个。

否则,把询问挂在 \(r1\) 上,这种情况下被挂上的颜色种数最多 \(\sqrt n\) ,最多共挂 \(\sqrt n\)

注意处理相同的询问,否则一种颜色在一个点上被挂多次就萎了。

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
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<map>
#include<algorithm>
#define mp make_pair
#define X first
#define Y second
typedef long long LL;
using namespace std;
const int maxn=200005,maxe=maxn;
int n,m,Q,a[maxn],cnt[maxn];
int fir[maxn],nxt[maxe],son[maxe],tot;
int smto[maxn];
LL ans[maxn];
map< pair<int,int>, int> M;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
vector< pair<int,int> > v1[maxn],v2[maxn];
int f[maxn],dfn[maxn],out[maxn],Tim;
void dfs2(int x){
for(int i=0;i<v2[a[x]].size();i++)
ans[v2[a[x]][i].Y]+=f[v2[a[x]][i].X];
f[a[x]]++;
for(int j=fir[x];j;j=nxt[j]) dfs2(son[j]);
f[a[x]]--;
}
void dfs1(int x){
for(int i=0;i<v1[a[x]].size();i++)
ans[v1[a[x]][i].Y]-=f[v1[a[x]][i].X];
f[a[x]]++;
for(int j=fir[x];j;j=nxt[j]) dfs1(son[j]);
for(int i=0;i<v1[a[x]].size();i++)
ans[v1[a[x]][i].Y]+=f[v1[a[x]][i].X];
}
int main(){
freopen("bzoj3351.in","r",stdin);
freopen("bzoj3351.out","w",stdout);
scanf("%d%d%d",&n,&m,&Q);
scanf("%d",&a[1]);
for(int i=2;i<=n;i++){
int x; scanf("%d%d",&x,&a[i]);
add(x,i);
}
for(int i=1;i<=n;i++) cnt[a[i]]++;
int Blk=sqrt(n)+1;
for(int i=1;i<=Q;i++){
int x,y; scanf("%d%d",&x,&y);
if(M[mp(x,y)]){ smto[i]=M[mp(x,y)]; continue; }
M[mp(x,y)]=i;
if(cnt[y]<=Blk) v2[y].push_back(mp(x,i));
else v1[x].push_back(mp(y,i));
}
dfs1(1);
memset(f,0,sizeof(f)); dfs2(1);
for(int i=1;i<=Q;i++){
if(smto[i]) ans[i]=ans[smto[i]];
printf("%lld\n",ans[i]);
}
return 0;
}