poj 2777 Counting Colors

poj 2777 Counting Colors

單線段樹單記錄的套路，記錄的是這個區間一致的顏色或者0

技巧是這個顏色可以用1 << (color - 1)來表示，這樣結果就是所有收集的顏色取或運算，數一數有多少個1就行了。

這個一致性體現在以下合並與分割時的過程，分割只需要把一致顏色放下去（為0就不放了），合並時只有兩側區間顏色一致才記錄

#define tree_merge       tree_obj = tree[root<<1] == tree[root<<1|1] ? tree[root << 1] : 0
#define tree_split       decl_mid; if(tree_obj){tree[root<<1]=tree[root<<1|1] = tree_obj; tree_obj = 0;}

#include 
#include 
#include 
#include 
#define FRAME       tree_frame
#define eq(x, y)    (!strcmp((x), (y)))
#define times(n, i)    for(int i=0; i= sl && r <= sr)
#define TAG_OUTSIDE      (l >= sr || r <= sl)
#define TAG_LEAF         (l == r-1)
#define decl_mid         int mid = (l + r) / 2;
#define recur_left       l, mid, root << 1
#define recur_right      mid, r, root << 1 | 1
void build(FRAME){
  if(TAG_LEAF){ tree_obj = 1; return; }
  tree_split;
  build(recur_left); build(recur_right);
  tree_merge;  
}	

void update(int value, int sl, int sr, FRAME){
//printf("%d %d %d %d %d %d\n", value, sl, sr, l, r, root);
  if(TAG_INSIDE) { 
    tree_obj = 1 << (value - 1);
    return ;
  }
  if(TAG_OUTSIDE){ return; }
  tree_split;
  update(value, sl, sr, recur_left ); 
  update(value, sl, sr, recur_right);
  tree_merge;
}

int result;
void query_impl(int sl, int sr, FRAME){
  if(TAG_INSIDE){ 
	  if(tree_obj != 0){
	     result |= tree_obj; 
	     return; 
	  }
  }
  if(TAG_OUTSIDE){ return; }
  tree_split;
  query_impl(sl, sr, recur_left);
  query_impl(sl, sr, recur_right);
  tree_merge;
}

int query(int sl, int sr){
  result = 0;
  query_impl(sl, sr);  
  int ans = 0;
 // printf("%x\n", result);
  while(result > 0) ans += result & 1, result >>= 1;
  return ans;
}


	
int main(){
     scanf("%d%d%d", &N, &T, &M);
     build();
     while(M--){
	int a, b, c;
	char tmp[1024];
	scanf("%s%d%d", tmp, &a, &b);
	if(a > b) std::swap(a, b);
	if(eq(tmp, "C")) {
  	  scanf("%d", &c);
	  update(c, a, b+1);
	}
	if(eq(tmp, "P")){
	  printf("%d\n", query(a, b+1));
	}
     }
  return 0;
}