题目描述

输入输出格式

输入格式：

 

 

输出格式：

 

对于每个询问操作，输出一行答案。

 

输入输出样例

输入样例#1：

6 52 2 1 2 1 11 21 32 42 52 6Q 3 5C 2 1 1Q 3 5C 5 1 2Q 3 5

输出样例#1：

312

说明

树链剖分。

#include
         
          #include
          
           #include
           
            #include
            
             const int N=100001;using namespace std;vector
             
              vec[N];int n,m,num,tot,colure[N];int deep[N],size[N],dad[N],top[N],id[N];struct nond{    int l,r,flag;    int l_colure,r_colure,sum;}tree[N*2];int dfs(int x){    size[x]=1;    deep[x]=deep[dad[x]]+1;    for(int i=0;i
              
               size[t]) t=vec[x][i]; if(t){ top[t]=top[x]; dfs1(t); } for(int i=0;i
               
                mid) change(r,t,x); up(now);}void down(int now){ if(tree[now].l==tree[now].r) return; int l=now+1,r=now+(tree[now+1].r-tree[now+1].l+1)*2; tree[l].l_colure=tree[r].l_colure=tree[l].r_colure=tree[r].r_colure=tree[l].flag=tree[r].flag=tree[now].flag; tree[l].sum=tree[r].sum=1; tree[now].flag=0;}void change_many(int now,int pol,int por,int a){ if(tree[now].l==pol&&tree[now].r==por){ tree[now].flag=tree[now].l_colure=tree[now].r_colure=a; tree[now].sum=1; return; } if(tree[now].flag) down(now); int mid=(tree[now].l+tree[now].r)/2; int l=now+1,r=now+(tree[now+1].r-tree[now].l+1)*2; if(por<=mid) change_many(l,pol,por,a); else if(pol>mid) change_many(r,pol,por,a); else{ change_many(l,pol,mid,a); change_many(r,mid+1,por,a); } up(now);}int change_ans(int u,int v,int a){ while(top[u]!=top[v]){ if(deep[top[u]]
                
                 id[v]) swap(u,v); change_many(1,id[u],id[v],a);}int query(int now,int t){ if(tree[now].l==tree[now].r) return tree[now].flag; if(tree[now].flag) down(now); int mid=(tree[now].l+tree[now].r)/2; int l=now+1,r=now+(tree[now+1].r-tree[now+1].l+1)*2; if(t<=mid) query(l,t); else query(r,t);}int query_many(int now,int pol,int por){ if(tree[now].l==pol&&tree[now].r==por){ return tree[now].sum; } if(tree[now].flag) down(now); int mid=(tree[now].l+tree[now].r)/2; int l=now+1,r=now+(tree[now+1].r-tree[now+1].l+1)*2; if(por<=mid) return query_many(l,pol,por); else if(pol>mid) return query_many(r,pol,por); else{ int t=query_many(l,pol,mid)+query_many(r,mid+1,por); if(tree[l].r_colure==tree[r].l_colure) t--; return t; }} void query_ans(int u,int v){ int ans=0; while(top[u]!=top[v]){ if(deep[top[u]]
                 
                  id[v]) swap(u,v); ans+=query_many(1,id[u],id[v]); cout<
                  
                   <
                   
                    >ch; if(ch=='C'){ scanf("%d%d%d",&a,&b,&c); change_ans(a,b,c); } else{ scanf("%d%d",&a,&b); query_ans(a,b); } } return 0;}