#include <iostream>

using namespace std;

struct node {
  long l,r;
  long color;
  long ans;       
};

node tree[300010];
long twice[31];
long L,n,T,ans,ccount;
long start,ended,color,total;

void init()
{
  long i;
  twice[0]=1;
  for (i=1;i<31;i++) twice[i]=2*twice[i-1];
}

long build_tree(long b,long e)
{
  long mark,mid;
  if (b==e) {
    tree[ccount].color=0; tree[ccount].ans=0;
    tree[ccount].l=-1; tree[ccount].r=-1; ccount++;
    return ccount-1;
  }
  mark=ccount; ccount++; mid=(b+e)/2;
  tree[mark].color=0; tree[mark].ans=0;
  tree[mark].l=build_tree(b,mid);
  tree[mark].r=build_tree(mid+1,e);
  return mark;
}

void paint(long b,long e,long k)
{
  long l,r,mid;
  if (ended<b||start>e) return;
  if (color==tree[k].color) return;
  if (start<=b&&ended>=e) {
    tree[k].color=color; tree[k].ans=twice[color-1];
    return;
  }
  l=tree[k].l; r=tree[k].r;
  if (tree[k].color!=-1) {
    tree[l].color=tree[k].color; tree[l].ans=tree[k].ans;                
    tree[r].color=tree[k].color; tree[r].ans=tree[k].ans;
    tree[k].color=-1;
  }
  mid=(b+e)/2;
  paint(b,mid,l); paint(mid+1,e,r);
  tree[k].ans=tree[l].ans|tree[r].ans;
  if (tree[l].color==tree[r].color&&tree[l].color!=-1) tree[k].color=tree[l].color;
}

void ask(long b,long e,long k)
{
  long mid;
  if (ended<b||start>e) return;
  if (start<=b&&ended>=e) {total=total|tree[k].ans; return;}
  if (tree[k].color!=-1) {total=total|tree[k].ans; return;}
  mid=(b+e)/2;
  ask(b,mid,tree[k].l); ask(mid+1,e,tree[k].r);
}

void work()
{
  long i,j,t;
  char temp;
  ccount=0;
  build_tree(0,L-1);
  tree[0].color=1; tree[0].ans=1;
  for (i=0;i<n;i++) {
    cin >> temp >> start >> ended;
    if (start>ended) {t=start; start=ended; ended=t;}
    start--; ended--;
    if (temp=='C') {
      cin >> color;
      paint(0,L-1,0);
    }
    if (temp=='P') {
      total=0; ask(0,L-1,0); ans=0;
      for (j=0;j<T;j++) if ((total&twice[j])!=0) ans++;
      cout << ans << endl;
    }
  }
}

int main()
{
  while (cin >> L >> T >> n)
  {
    init();
    work();
  }
  return 0;    
}

• Re:WHY TLE?? (13) kenin 2006-03-27 17:31:53