Description
Input
Output
Sample Input
2 2 4 C 1 1 2 P 1 2 C 2 2 2 P 1 2
Sample Output
2 1
看了网上不少的题解，感觉没有那么麻烦。。就是区间更新，每次统计数量的时候哈希一下就好，详见代码。
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
#include <ctype.h>
#define lson o << 1, l, m
#define rson o << 1|1, m+1, r
using namespace std;
typedef long long LL;
const int MAX = 0x3f3f3f3f;
const int maxn = 100010;
int n, a, b, c, t, q, ans;
char s[3];
int cnt[maxn<<2], vis[35];
void down(int o) {
if(cnt[o]) {
cnt[o<<1] = cnt[o<<1|1] = cnt[o];
cnt[o] = 0;
}
}
void build(int o, int l, int r) {
cnt[o] = 1;
if(l == r) return;
int m = (l+r) >> 1;
build(lson);
build(rson);
}
void update(int o, int l, int r) {
if(a <= l && r <= b) {
cnt[o] = c;
return;
}
down(o);
int m = (l+r) >> 1;
if(a <= m) update(lson);
if(m < b ) update(rson);
}
void query(int o, int l, int r) {
if(cnt[o]) {
if(vis[ cnt[o] ] == 0) {
ans ++;
vis[ cnt[o] ] = 1;
}
return ;
}
int m = (l+r) >> 1;
if(a <= m) query(lson);
if(m < b ) query(rson);
}
int main()
{
scanf("%d%d%d", &n, &t, &q);
build(1, 1, n);
while(q--) {
scanf("%s%d%d", s, &a, &b);
if(a > b) swap(a, b);
if(s[0] == 'C') {
scanf("%d", &c);
update(1, 1, n);
} else {
memset(vis, 0, sizeof(vis));
ans = 0;
query(1, 1, n);
printf("%d\n", ans);
}
}
return 0;
}
POJ 2777 Count Color （线段树区间更新加查询）,布布扣,bubuko.com
POJ 2777 Count Color （线段树区间更新加查询）
原文：http://blog.csdn.net/u013923947/article/details/38542633