小奇的花园-白红宇

小奇的花园

阅读量：5221 次

发布时间：2019-06-14

本文共 3866 字，大约阅读时间需要 12 分钟。

【问题描述】

小奇的花园有 n 个温室,标号为 1 到 n,温室以及以及温室间的双向道路形成一

棵树。

每个温室都种植着一种花,随着季节的变换,温室里的花的种类也在不断发生着

变化。

小奇想知道从温室 x 走到温室 y 的路径中(包括两个端点),第 t 种花出现的次数。

【输入格式】

第一行为两个整数 n,q,表示温室的数目和操作的数目。

第二行有 n 个整数 T 1 ,T 2 ...T n 其中 T i 表示温室 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

【样例输出】

【样例解释】

加密前的操作:

Q 2 5 10

C 3 20

Q 2 5 20

C 4 20

Q 3 5 30

C 5 20

Q 2 5 20Q 1 3 10

【数据范围】

对于 30%的数据,有 n <= 1000, q <= 2000。

对于 50%的数据,有 n <= 10000, q <= 20000。

对于 100%的数据,有 n <= 100000, q <= 200000,0 <= T <= 2^31。

树链剖分

对于每一种颜色建一棵线段树，动态开点

颜色用map离散，最多300000种颜色

动态开店用内存池防止内存超限

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
           7 #include
           
             8 using namespace std; 9 struct Node 10 { 11 int next,to; 12 }edge[200001]; 13 queue
            
             Q; 14 int num,head[100001],pos,tot,cnt,dep[100001],fa[100001],size[100001],son[100001]; 15 int top[100001],dfn[100001],root[300001],t[300001],ans,c[10000001],ch[10000001][2],n,q; 16 map
             
              mp; 17 void add(int u,int v) 18 { 19 num++; 20 edge[num].next=head[u]; 21 head[u]=num; 22 edge[num].to=v; 23 } 24 void dfs1(int x,int pa) 25 { int i; 26 dep[x]=dep[pa]+1; 27 fa[x]=pa; 28 size[x]=1; 29 for (i=head[x];i;i=edge[i].next) 30 { 31 int v=edge[i].to; 32 if (v==pa) continue; 33 dfs1(v,x); 34 size[x]+=size[v]; 35 if (size[v]>size[son[x]]) son[x]=v; 36 } 37 } 38 void dfs2(int x,int pa,int tp) 39 { int i; 40 top[x]=tp; 41 dfn[x]=++tot; 42 if (son[x]) dfs2(son[x],x,tp); 43 for (i=head[x];i;i=edge[i].next) 44 { 45 int v=edge[i].to; 46 if (v==pa||son[x]==v) continue; 47 dfs2(v,x,v); 48 } 49 } 50 int query(int rt,int l,int r,int L,int R) 51 { 52 if (!rt) return 0; 53 if (l>=L&&r<=R) return c[rt]; 54 int mid=(l+r)/2,as=0; 55 if (L<=mid) as+=query(ch[rt][0],l,mid,L,R); 56 if (R>mid) as+=query(ch[rt][1],mid+1,r,L,R); 57 return as; 58 } 59 int ask(int x,int y,int c) 60 { 61 int as=0; 62 while (top[x]!=top[y]) 63 { 64 if (dep[top[x]]
              
               dep[y]) swap(x,y); 69 as+=query(root[c],1,n,dfn[x],dfn[y]); 70 return as; 71 } 72 void update(int &rt,int l,int r,int x) 73 { 74 if (!rt) 75 { 76 if (Q.empty()==0) rt=Q.front(),Q.pop(); 77 else rt=++pos; 78 } 79 c[rt]++; 80 if (l==r) return; 81 int mid=(l+r)/2; 82 if (x<=mid) update(ch[rt][0],l,mid,x); 83 else update(ch[rt][1],mid+1,r,x); 84 } 85 void del(int &rt,int l,int r,int x) 86 { 87 c[rt]--; 88 if (l==r&&c[rt]==0) 89 { 90 Q.push(rt); 91 rt=0; 92 } 93 if (l==r) return; 94 int mid=(l+r)/2; 95 if (x<=mid) del(ch[rt][0],l,mid,x); 96 else del(ch[rt][1],mid+1,r,x); 97 if (c[rt]==0) 98 { 99 ch[rt][0]=ch[rt][1]=0;100 Q.push(rt);101 rt=0;102 }103 }104 int main()105 { int i,u,v,x,y,c;106 char s[21];107 cin>>n>>q;108 for (i=1;i<=n;i++)109 {110 scanf("%d",&t[i]);111 if (mp.count(t[i])==0) mp[t[i]]=++cnt;112 t[i]=mp[t[i]];113 }114 for (i=1;i<=n-1;i++)115 {116 scanf("%d%d",&u,&v);117 add(u,v);add(v,u);118 }119 dfs1(1,0);120 dfs2(1,0,1);121 for (i=1;i<=n;i++)122 {123 update(root[t[i]],1,n,dfn[i]);124 }125 ans=0;126 while (q--)127 {128 scanf("%s",s);129 if (s[0]=='Q')130 {131 scanf("%d%d%d",&x,&y,&c);132 x^=ans;y^=ans;c^=ans;133 ans=0;134 if (mp.count(c)==0)135 {136 printf("0\n");137 continue;138 }139 c=mp[c];140 ans=ask(x,y,c);141 printf("%d\n",ans);142 }143 else144 {145 scanf("%d%d",&x,&c);146 x^=ans;c^=ans;147 del(root[t[x]],1,n,dfn[x]);148 if (mp.count(c)==0) mp[c]=++cnt;149 t[x]=mp[c];150 update(root[t[x]],1,n,dfn[x]);151 }152 }153 }