bzoj3351 [ IOI2009 ] -- 阈值

2018-06-17 23:19:00来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

题目大意:

给定一棵有根树,每次询问所有颜色为a的节点的子树中颜色为b的节点个数之和。

 

思路:

考虑将询问按b的出现次数分类。

若b<=sqrt(n),我们可以在每个b节点用一个vector记录它涉及到的询问。

dfs,用桶记录从根节点到这个节点每种颜色的出现次数,就可以更新答案了。

由于总点数为O(q*sqrt(n)),时间复杂度为O(q*sqrt(n))

若b>sqrt(n),那么只有不超过sqrt(n)种这样的颜色,我们可以在每个a节点用一个vector记录它涉及到的询问。

dfs,用桶记录子树中各颜色出现次数,更新答案。时间复杂度为O(n*sqrt(n))

所以总时间复杂度为O(q*sqrt(n)+n*sqrt(n))

具体看代码

代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<vector>
 6 #include<cmath>
 7 #include<map>
 8 using namespace std;
 9 inline char nc(){
10   static char buf[100000],*p1=buf,*p2=buf;
11   if(p1==p2){
12     p2=(p1=buf)+fread(buf,1,100000,stdin);
13     if(p1==p2)return EOF;
14   }
15   return *p1++;
16 }
17 inline void Read(int& x){
18   char c=nc();
19   for(;c<'0'||c>'9';c=nc());
20   for(x=0;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-48,c=nc());
21 }
22 #define N 200010
23 #define R 25010
24 #define ll long long
25 struct Node{
26   int x,y;
27   Node(){}
28   Node(int x,int y):x(x),y(y){}
29   bool operator<(Node a)const{
30     return x<a.x||(x==a.x&&y<a.y);
31   }
32 }b[N];
33 map<Node,int>M;
34 vector<int>g[N],B[N],A[N];
35 int n,r,q,f[N],a[N],S,Tmp[R],Sum[R],i,F[N];
36 ll Ans[N];
37 inline void Dfs1(int x){
38   Tmp[a[x]]++;
39   for(int i=0;i<B[a[x]].size();i++)Ans[B[a[x]][i]]+=Tmp[b[B[a[x]][i]].x];
40   for(int i=0;i<g[x].size();i++)Dfs1(g[x][i]);
41   Tmp[a[x]]--;
42 }
43 inline void Dfs2(int x){
44   for(int i=0;i<A[a[x]].size();i++)
45     Ans[A[a[x]][i]]-=Tmp[b[A[a[x]][i]].y];
46   Tmp[a[x]]++;
47   for(int i=0;i<g[x].size();i++)Dfs2(g[x][i]);
48   for(int i=0;i<A[a[x]].size();i++)
49     Ans[A[a[x]][i]]+=Tmp[b[A[a[x]][i]].y];
50 }
51 char s[30];
52 int Len;
53 inline void Print(ll x){
54   if(x==0)putchar(48);
55   for(Len=0;x;x/=10)s[++Len]=x%10;
56   for(;Len;)putchar(s[Len--]+48);
57   putchar('\n');
58 }
59 int main()
60 {
61   Read(n);Read(r);Read(q);
62   S=(int)sqrt((double)n)+1;Read(a[1]);Sum[a[1]]++;
63   for(i=2;i<=n;i++)Read(f[i]),g[f[i]].push_back(i),Read(a[i]),Sum[a[i]]++;
64   for(i=1;i<=q;i++){
65     Read(b[i].x);Read(b[i].y);F[i]=i;
66     if(M.count(Node(b[i].x,b[i].y)))F[i]=M[Node(b[i].x,b[i].y)];else{
67       M[Node(b[i].x,b[i].y)]=i;
68       if(Sum[b[i].y]<=S)B[b[i].y].push_back(i);else A[b[i].x].push_back(i);
69     }
70   }
71   Dfs1(1);Dfs2(1);
72   for(i=1;i<=q;i++)Print(Ans[F[i]]);
73   return 0;
74 }
bzoj3351

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:bzoj1497 [ NOI2006 ] --最大权闭合子图

下一篇:C++ 头文件系列(sstream)