洛谷P 1558色板ゲーム

テーマの背景
宝さんは学校に行きました.今日先生は長い塗装板を持ってきました.
タイトルの説明
色板の長さはLで、Lは正の整数なので、Lブロックの長さ1センチの小さな四角形に均一に分けることができます.左から1,2,...Lとマークします.今色板の上でただ1つの色だけあって、先生は宝に色板の上で2つの事しかできないことを教えます:1.「C A B C」とは、AからB番の格子に色Cを塗ることを意味する.2.「P A B」は先生の質問です.AからB番の四角い格子にはいくつかの色があります.学校の絵の具箱には全部でT種類の絵の具が入っています.簡単にするために、私たちは彼らを1,2,...T.とマークしました.最初は色板の元の色が1番の色でした.このような複雑な問題に直面して、宝さんはあなたに助けを求めて、あなたは彼を助けることができますか?
にゅうしゅつりょくけいしき
入力フォーマット:1行目に3個の整数L(1<=L<=100000)、T(1<=T<=30)、O(1<=O<=100000)がある.ここでOはイベント数を表し、次にO行、各行は「C A B C」または「P A B」の形でやるべきことを表す(ここではA,B,Cは整数であり、A>Bである可能性がある)
出力フォーマット:先生の質問に対して、相応の答えを出します.行ごとに整数を指定します.
入出力サンプル
入力サンプル#1:2 2 2 4 C 1 1 1 2 P 1 2 C 2 2 2 P 1 2出力サンプル#1:2

#include
#include
#include
#include
#include
#include
using namespace std;
struct Node{
    int l,r,col[31],sum,lazy_change;
    Node *son[2];
}*root;
int L,T,O;
void UpDate(Node *cur){
    for(int i=1;i<=T;i++){
        cur->col[i] = cur->son[0]->col[i] +
                            cur->son[1]->col[i];
        if(cur->col[i]) cur->sum++;
     }
    return;
}
void Built(Node *&cur,int l,int r){
    cur = new Node;
    cur->l=l; cur->r=r;
    cur->sum=0; cur->lazy_change=0;
    for(int i=1;i<=T;i++) cur->col[i] = 0;
    if(l==r){
        cur->col[1]=1;cur->sum=1;
        return;
    }
    int mid=(l+r)>>1;
    Built(cur->son[0],l,mid);
    Built(cur->son[1],mid+1,r);
    UpDate(cur);
    return;
}
void Down(Node* cur){
    for(int i=1;i<=T;i++) 
        cur->son[0]->col[i] = cur->son[1]->col[i] =0;
    cur->son[0]->col[ cur->lazy_change ] 
            = cur->son[1]->col[ cur->lazy_change ] = 1;
    cur->son[1]->lazy_change = 
        cur->son[0]->lazy_change = cur->lazy_change;
    cur->son[1]->sum = cur->son[0]->sum = 1;
    cur->lazy_change=0;
}
void Change(Node* cur,int l,int r,int x){
    if(l == cur->l&&cur->r ==r){
        cur->sum=1;
        for(int i=1;i<=T;i++) cur->col[i]=0;
        cur->col[x]=1;cur->lazy_change=x;
        return ;
    }
    if(cur->lazy_change) Down(cur);
    int mid=(cur->l + cur->r)>>1;
    if(l>mid) Change(cur->son[1],l,r,x);
    else if(r<=mid) Change(cur->son[0],l,r,x);
    else Change(cur->son[0],l,mid,x),
            Change(cur->son[1],mid+1,r,x);
    UpDate(cur);
}
int flag[35];
void Query(Node* cur,int l,int r){
    if(l == cur->l && cur->r == r){
        for(int i=1;i<=T;i++) flag[i] += cur->col[i];
        return ;
    }
    if(cur->lazy_change) Down(cur);
    int mid=(cur->l + cur->r) >>1;
    if(l>mid)  Query(cur->son[1],l,r);
    else if(r<=mid)  Query(cur->son[0],l,r);
    else Query(cur->son[0],l,mid)
            ,Query(cur->son[1],mid+1,r);
    return ;
}
int solve(){
    int ans=0;
    for(int i=1;i<=T;i++) if(flag[i]) ans++;
    return ans;
}
int main(){
    scanf("%d%d%d",&L,&T,&O);
    Built(root,1,L);
    char C;
    int L,R,X;
    while(O--){
        cin>>C;
        if(C=='C'){
            scanf("%d%d%d",&L,&R,&X);
            if(L>R) swap(L,R);
            Change(root,L,R,X);
        }
        else if(C=='P'){
            scanf("%d%d",&L,&R);
            if(L>R) swap(L,R);
            memset(flag,0,sizeof flag );
            Query(root,L,R);
            printf("%d
",solve());
        }
    }
    return 0;
}