線分ツリー-POJ 2777


これは統計的な問題であるが、2つの操作が与えられ、C A B color:区間[A,B]に色colorを塗り、P A Bは区間[A,B]の色の数を統計して印刷し、図色の種類は30種類を超えず、区間の長さは最大100000に達し、与えられた操作回数は最大100000に達する.
これは古典的な線分ツリーのテーマで、色の数は最大30種類しかないため、32ビット整形の各ビットで対応する色を表すことができ、集約の操作を容易にすることができます.
#include<cstdio>
#include<cstring>
#include<iostream>
#define N 100100

using namespace std;

int l,t,o;
long long int color[N<<2];

int count(int k)//            1
{
    int ans=0;
    while(k>0)
    {
          ans++;
          k-=(k&(-k));//           K     1    
//                 
    }
    return ans;
}

void update(int rt,int ld,int rd,int s,int e,long long int c)
{
     if(s<=ld && rd<=e) {
         color[rt]=c;
         return ;
     }
     int mid=(ld+rd)>>1;
     int cnt = count(color[rt]);
     if(cnt==1) {color[rt<<1]=color[rt];color[rt<<1|1]=color[rt];}
     if(e<=mid) update(rt<<1,ld,mid,s,e,c);
     else if(s>mid) update(rt<<1|1,mid+1,rd,s,e,c);
     else {
          update(rt<<1,ld,mid,s,mid,c);
          update(rt<<1|1,mid+1,rd,mid+1,e,c);
     }
     color[rt]=color[rt<<1]|color[rt<<1|1];
}

int query(int rt,int ld,int rd,int s,int e)
{
    if(s<=ld && rd<=e) return color[rt];
    int mid=(ld+rd)>>1;
    int cnt=count(color[rt]);
    if(cnt==1) return color[rt];
    if(e<=mid) return query(rt<<1,ld,mid,s,e);
    else if(s>mid) return query(rt<<1|1,mid+1,rd,s,e);
    else {
         int c1=query(rt<<1,ld,mid,s,mid);
         int c2=query(rt<<1|1,mid+1,rd,mid+1,e);
         return c1|c2;
    }
}

void getline(char *s)
{
     char ch;
     int i=0;
     while(true) {
         scanf("%c",&ch);
         s[i++]=ch;
         if(ch=='
') break; } s[i]='\0'; } int main() { while(scanf("%d%d%d",&l,&t,&o)!=EOF){ char str[20],ch; for(int i=0;i<4*N;i++) color[i]=1; scanf("%c",&ch); for(int i=0; i<o; i++) { getline(str); int a,b,c; sscanf(str,"%c%d%d",&ch,&a,&b); int temp = a; if(a>b) { a=b; b=temp; } if (ch=='C') { sscanf(str,"%c%d%d%d",&ch,&a,&b,&c); update(1,1,l,a,b,1<<(c-1)); } if(ch=='P') printf("%d
", count(query(1,1,l,a,b))); } } return 0; }