【NOI省选模拟】小奇的花园

「题目背景」

小奇在家中的花园漫步时，总是会思考一些奇怪的问题。

「问题描述」

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

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

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

「输入格式」

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

第二行有n个整数T1，T2…Tn其中Ti表示温室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

「样例输出」

1

2

0

3

1

「样例解释」

加密前的操作:

Q 2 5 10

C 3 20

Q 2 5 20

C 4 20

Q 3 5 30

C 5 20

Q 2 5 20

Q 1 3 10

「数据范围」

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

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

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

---

  ←小奇

下面的题解都是自己的话：

50%

既然强制在线，那我们就在线模拟，没什么方法，就一步步地往上找LCA并统计答案然后输出就好啦~

考场上实在没办法AC拿50分也不吃亏。

100%

有一个转化很重要。

我们可以通过类似求树上两点路径长度 dis=dep[x]+dep[y]-dep[LCA]*2 的方法，用s[i]表示从根节点到此时的i点col颜色的出现次数。

所以每次在某个节点的某个颜色出现次数增加1时，它的整个子树的每个节点的s[i]都会增加1，那么从x到y某个颜色的出现次数显然就变成 s[x]+s[y]-s[LCA]*2+val[LCA]了

那这样题目要求的单点修改、区间查询就被我们变成子树修改、单点查询了。子树修改用DFS序来看其实也就是区间修改了，可以用线段树解决。

但是颜色种类那么多怎么办呢（而且数值还那么大）？

可以用map来维护颜色编号，用动态开点线段树的方式对每一种颜色维护一棵线段树。

做本题是参考了黄学长Hzwer的题解和程序，代码可能有相似之处，但线段树的操作绝对是我自己的风格。（求资瓷~）

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<map>

 #define For(i,a,b)for(register int i=a;i<=b;++i)

 #define Dwn(i,a,b)for(register int i=a;i>=b;--i)

 #define Re register

 #define Pn putchar('\n')

 using namespace std;

 const int N=1e5+,Nr=1e7+;

 int head[N],nxt[N*],v[N*],cnt=;

 int f[N][],dfx[N],dID=,dep[N],sz[N];

 int rt[N*],ls[Nr],rs[Nr],tag[Nr],tr[Nr],tID=;

 int n,m,x,y,T[N*],cID=,t,Q,ans=;

 map<int,int>mp;

 inline void read(int &v){

     v=;

     char c=getchar();

     while(c<''||c>'')c=getchar();

     while(c>=''&&c<='')v=v*+c-'',c=getchar();

 }

 void write(int x){

     if(x>)write(x/);

     int xx=x%;

     putchar(xx+'');

 }

 void add(int ux,int vx){

     cnt++;

     nxt[cnt]=head[ux]; head[ux]=cnt; v[cnt]=vx;

     cnt++;

     nxt[cnt]=head[vx]; head[vx]=cnt; v[cnt]=ux;

 }

 void DFS(int x,int fa){

     sz[x]=;

     dfx[x]=++dID;

     for(Re int i=head[x];i;i=nxt[i]){

         int vv=v[i];

         if(vv==fa)continue;

         dep[vv]=dep[x]+;

         f[vv][]=x;

         DFS(vv,x);

         sz[x]+=sz[vv];

     }

 }

 int LCA(int x,int y){

     if(dep[x]<dep[y])swap(x,y);

     Dwn(b,,)if(f[x][b]!=-){

         if(dep[f[x][b]]>=dep[y])x=f[x][b];

     }

     if(x==y)return x;

     Dwn(b,,)if(f[x][b]!=-&&f[y][b]!=-&&f[x][b]!=f[y][b]){

         x=f[x][b]; y=f[y][b];

     }

     return f[x][];

 }

 void pDown(int o,int l,int r){

     if(!tag[o]||l==r)return;

     int tg=tag[o]; tag[o]=;

     if(!ls[o])ls[o]=++tID;

     if(!rs[o])rs[o]=++tID;

     tr[ls[o]]+=tg; tag[ls[o]]+=tg;

     tr[rs[o]]+=tg; tag[rs[o]]+=tg;

 }

 void Ins(int &o,int l,int r,int lx,int rx,int dt){

     if(!o)o=++tID;

     if(lx<=l&&rx>=r){

         tr[o]+=dt; tag[o]+=dt;

         return;

     }

     pDown(o,l,r);

     int m=(l+r)>>;

     if(lx<=m)Ins(ls[o],l,m,lx,rx,dt);

     if(rx>m)Ins(rs[o],m+,r,lx,rx,dt);

 }

 int Qry(int o,int l,int r,int px){

     if(!o)return ;

     if(l==r)return tr[o];

     pDown(o,l,r);

     int m=(l+r)>>;

     if(px<=m)return Qry(ls[o],l,m,px);

     else return Qry(rs[o],m+,r,px);

 }

 int main(){

     freopen("garden.in","r",stdin);

     freopen("garden.out","w",stdout);

     read(n); read(Q);

     For(i,,n){

         read(t);

         if(!mp[t])mp[t]=++cID;

         T[i]=mp[t];

     }

     For(i,,n-){

         read(x); read(y);

         add(x,y);

     }

     memset(f,-,sizeof(f));

     DFS(,);

     For(b,,) For(i,,n){

         if(f[i][b-]==-)continue;

         f[i][b]=f[ f[i][b-] ][b-];

     }

     For(i,,n){

         int lx=dfx[i];

         int rx=dfx[i]+sz[i]-;

         Ins(rt[T[i]],,n,lx,rx,);

     }

     For(i,,Q){

         char opt=getchar();

         while(opt!='C'&&opt!='Q')opt=getchar();

         if(opt=='C'){

             read(x); read(t);

             x^=ans; t^=ans;

             if(!mp[t])mp[t]=++cID;

             t=mp[t];

             int lx=dfx[x],rx=dfx[x]+sz[x]-;

             Ins(rt[T[x]],,n,lx,rx,-);

             Ins(rt[t],,n,lx,rx,);

             T[x]=t;

         }

         if(opt=='Q'){

             read(x); read(y); read(t);

             x^=ans; y^=ans; t^=ans;

             if(!mp[t])mp[t]=++cID;

             t=mp[t];

             int xy=LCA(x,y);

             int fn;

             fn=Qry(rt[t],,n,dfx[x])+Qry(rt[t],,n,dfx[y]);

             fn-=Qry(rt[t],,n,dfx[xy])*;

             if(T[xy]==t)fn++;

             ans=fn;

             write(fn); Pn;

         }

     }

     fclose(stdin); fclose(stdout);

     return ;

 }

【NOI省选模拟】小奇的花园的相关教程结束。