BZOJ4999：This Problem Is Too Simple！（DFS序&树上差分&线段树动态开点：区间修改单点查询）

Description

给您一颗树，每个节点有个初始值。

现在支持以下两种操作：

1. C i x(0<=x<2^31) 表示将i节点的值改为x。

2. Q i j x(0<=x<2^31) 表示询问i节点到j节点的路径上有多少个值为x的节点。

Input

第一行有两个整数N,Q（1 ≤N≤ 100,000；1 ≤Q≤ 200,000），分别表示节点个数和操作个数。

下面一行N个整数，表示初始时每个节点的初始值。

接下来N-1行，每行两个整数x,y，表示x节点与y节点之间有边直接相连（描述一颗树）。

接下来Q行，每行表示一个操作，操作的描述已经在题目描述中给出。

Output

对于每个Q输出单独一行表示所求的答案。

Sample Input

5 6
10 20 30 40 50
1 2
1 3
3 4
3 5
Q 2 3 40
C 1 40
Q 2 3 40
Q 4 5 30
C 3 10
Q 4 5 30

Sample Output

0
1
1
0

题意：给定一个数，顶点有颜色。 Q次操作，或修改单点颜色，或查询路径颜色为x的个数。

思路：由于是路径，想到树剖+线段树，但是颜色个数无法合并，因此不行。换个思路，用差分来求，然后把每个颜色弄个线段树，然后这个颜色的线段树单点代表的是这个点到根有多少这个颜色。如果x点加了一个颜色为y的，那么以y这棵树，就再某个范围加1，这个范围是x的子树的DFS序范围；同理，减少则为-1 。

那么查询u到v路径为x颜色的个数，就在x这棵树上求sum[u]+sum[v]-sum[LCA]-sum[fa[LCA]];

自己写了一遍，感觉动态开点好像也没那么难。但是为什么我的那么慢啊。

（颜色需要离散化。

#include<bits/stdc++.h>

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

using namespace std;

const int maxn=;

struct in{

    int lson,rson,lazy;

    in(){lson=rson=lazy=;}

}s[maxn*];

struct qqq{

    char opt[]; int u,v,x;

}q[maxn<<];

int dep[maxn],a[maxn],rt[maxn*],fa[maxn][],in[maxn],ou[maxn],Log[maxn];

int Laxt[maxn],Next[maxn<<],To[maxn<<],cnt,times,b[maxn*],tot;

void add(int u,int v){

    Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v;

}

int LCA(int u,int v){

    if(dep[u]<dep[v]) swap(u,v);

    for(int i=Log[dep[u]-dep[v]];i>=;i--)

      if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];

    if(u==v) return u;

    for(int i=;i>=;i--)

      if(fa[u][i]!=fa[v][i]) u=fa[u][i],v=fa[v][i];

    return fa[u][];

}

void dfs(int u,int f){

    in[u]=++times;dep[u]=dep[f]+;

    for(int i=Laxt[u];i;i=Next[i])

      if(To[i]!=f) dfs(To[i],u);

    ou[u]=times; fa[u][]=f;

}

void pushdown(int Now){

    if(s[Now].lazy!=){

        if(!s[Now].lson) s[Now].lson=++cnt;

        if(!s[Now].rson) s[Now].rson=++cnt;

        s[s[Now].lson].lazy+=s[Now].lazy;

        s[s[Now].rson].lazy+=s[Now].lazy;

        s[Now].lazy=;

    }

}

void addnum(int &Now,int L,int R,int l,int r,int add){

    if(!Now) Now=++cnt;

    if(l<=L&&r>=R){ s[Now].lazy+=add; return ; }

    int Mid=(L+R)>>; pushdown(Now);

    if(l<=Mid)  addnum(s[Now].lson,L,Mid,l,r,add);

    if(r>Mid)  addnum(s[Now].rson,Mid+,R,l,r,add);

}

int query(int Now,int L,int R,int pos){

    if(!Now) return ;

    if(L==R) return s[Now].lazy;

    int Mid=(L+R)>>; pushdown(Now);

    if(pos<=Mid) return query(s[Now].lson,L,Mid,pos);

    return query(s[Now].rson,Mid+,R,pos);

}

int main()

{

    int N,Q,u,v,x;

    scanf("%d%d",&N,&Q);  rep(i,,N)   Log[i]=Log[i>>]+;

    rep(i,,N) scanf("%d",&a[i]),b[++tot]=a[i];

    rep(i,,N-){

        scanf("%d%d",&u,&v);

        add(u,v); add(v,u);

    }

    dfs(,); cnt=;

    rep(j,,)

     rep(i,,N){

        fa[i][j]=fa[fa[i][j-]][j-];

    }

    rep(i,,Q){

        scanf("%s%d%d",q[i].opt,&q[i].u,&q[i].v);

        if(q[i].opt[]=='Q') scanf("%d",&q[i].x),b[++tot]=q[i].x;

        else b[++tot]=q[i].v;

    }

    sort(b+,b+tot+); tot=unique(b+,b+tot+)-(b+);

    rep(i,,N) a[i]=lower_bound(b+,b+tot+,a[i])-b;

    rep(i,,Q) {

        if(q[i].opt[]=='Q') q[i].x=lower_bound(b+,b+tot+,q[i].x)-b;

        else q[i].v=lower_bound(b+,b+tot+,q[i].v)-b;

    }

    rep(i,,N) addnum(rt[a[i]],,N,in[i],ou[i],);

    rep(i,,Q){

        u=q[i].u; v=q[i].v;

        if(q[i].opt[]=='C'){

           addnum(rt[a[u]],,N,in[u],ou[u],-); a[u]=v;

           addnum(rt[a[u]],,N,in[u],ou[u],);

        }

        else {

           x=q[i].x;

           int Lca=LCA(u,v);

           int res=query(rt[x],,N,in[u]);

           res+=query(rt[x],,N,in[v]);

           res-=query(rt[x],,N,in[Lca]);

           res-=query(rt[x],,N,in[fa[Lca][]]);

           printf("%d\n",res);

        }

    }

    return ;

}

巴特西