PKU 2777 Count Color

http://poj.org/problem?id=2777
長さlの板に何回も色を塗っていく。
以下のようなクエリを処理しろといような問題。
・区間[a,b]を色cで塗る。
・区間[a,b]に何色の色が塗られているか答える。

セグメント木を頑張って書きました。
セグメント木は1色しか塗られていない領域まで深くしていっています。
塗るときに、色が増える場合は、もとあった色を一段下まで塗るようにしています。

int segtree[800000];

int paint(int l,int r,int k,int cl,int cr,int c){
  //cout<<"p "<<l<<' '<<r<<' '<<k<<' '<<cl<<' '<<cr<<' '<<c<<endl;
  if(l<=cl && cr<=r)
    return segtree[k]=c;

  if(cr<=l || r<=cl)return segtree[k];
  if(__builtin_popcount(segtree[k])<=1){
    paint(cl,cr,k*2+1,cl,(cl+cr)/2,segtree[k]);
    paint(cl,cr,k*2+2,(cl+cr)/2,cr,segtree[k]);
  }

  return
    segtree[k]=
    paint(l,r,k*2+1,cl,(cl+cr)/2,c)|
    paint(l,r,k*2+2,(cl+cr)/2,cr,c);
}


int count(int l,int r,int k,int cl,int cr){
  //cout<<"c "<<l<<' '<<r<<' '<<k<<' '<<cl<<' '<<cr<<endl;  
  if(r<=cl || cr<=l)return 0;
  if(l<=cl && cr<=r ||
     __builtin_popcount(segtree[k])<=1)
    return segtree[k];

  return
    count(l,r,k*2+1,cl,(cl+cr)/2)|count(l,r,k*2+2,(cl+cr)/2,cr);
}


main(){
  int l,t,o;
  scanf("%d%d%d",&l,&t,&o);
  int n=1;
  while(n<=l)n<<=1;
  paint(0,n,0,0,n,1);

  while(o--){
    /*
    int idx=0;
    cout<<endl;
    for(int i=1;i<=n;i*=2){
      for(int j=0;j<i;++j)
        printf("%d ",segtree[idx+j]);
      puts("");
      idx+=i;
    }
    cout<<endl;
    */
    char c;
    int a,b;
    scanf(" %c %d %d",&c,&a,&b);
    if(c=='P')
      printf("%d\n",__builtin_popcount(count(a,b+1,0,0,n)));
    else{
      int c;
      scanf("%d",&c);
      paint(a,b+1,0,0,n,1<<c-1);
    }
    //cout<<endl;
  }
}