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
这题做得真是有点……晕……区间更新没做过，所以处理颜色的时候不太会……本来想的是每段都记录哪种颜色，但是这个不会，所以直接2种颜色以上的就不把这些颜色都记录了，查询的时候再查询它的子树得了，本来以为这会时间更加多，但是没想到也挺快的，数据弱了！如果数组比较强的话，我这种方法可能会超时的……
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <list>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define PI acos(-1.0)
#define mem(a,b) memset(a,b,sizeof(a))
#define sca(a) scanf("%d",&a)
#define pri(a) printf("%d\n",a)
#define f(i,a,n) for(i=a;i<n;i++)
#define F(i,a,n) for(i=a;i<=n;i++)
#define MM 200005
#define MN 505
#define INF 10000007
using namespace std;
typedef long long ll;
char s[2];
int a,b,c,vis[31];
struct node
{
int l,r,lazy,mid;
} tree[MM*4];
void build(int i,int l,int r)
{
tree[i].l=l;
tree[i].r=r;
tree[i].lazy=1; //lazy有值时表示当前颜色，若为0表示有多种颜色
tree[i].mid=(l+r)>>1; //建树直接把中点算好，更新与查询就不用再算了
if(l==r) return;
build(i<<1,l,tree[i].mid);
build(i<<1|1,tree[i].mid+1,r);
}
void insert(int i,int l,int r,int lazy)
{
if(tree[i].l==l&&tree[i].r==r)
{
tree[i].lazy=lazy;
return ;
}
if(tree[i].lazy==lazy) return ;
if(tree[i].lazy)
{
tree[i<<1].lazy=tree[i<<1|1].lazy=tree[i].lazy;
tree[i].lazy=0;
}
if(l>tree[i].mid) insert(i<<1|1,l,r,lazy);
else if(r<=tree[i].mid) insert(i<<1,l,r,lazy);
else
{
insert(i<<1,l,tree[i].mid,lazy);
insert(i<<1|1,tree[i].mid+1,r,lazy);
}
}
void query(int i,int l,int r)
{
if(tree[i].lazy)
{
vis[tree[i].lazy]=1; //哪种颜色出现，重复时不变
return ;
}
if(l>tree[i].mid) query(i<<1|1,l,r);
else if(r<=tree[i].mid) query(i<<1,l,r);
else
{
query(i<<1,l,tree[i].mid);
query(i<<1|1,tree[i].mid+1,r);
}
}
int main()
{
int l,t,q;
scanf("%d%d%d",&l,&t,&q);
build(1,1,l);
while(q--)
{
scanf("%s%d%d",s,&a,&b);
if(s[0]==‘C‘)
{
scanf("%d",&c);
insert(1,a,b,c);
}
else
{
int sum=0; mem(vis,0);
query(1,a,b);
for(int i=1;i<=t;i++)
if(vis[i]) sum++; //出现颜色+1
pri(sum);
}
}
return 0;
}
CUGB专题训练之数据结构：B - Count Color 线段树区间更新,布布扣,bubuko.com
CUGB专题训练之数据结构：B - Count Color 线段树区间更新
原文：http://blog.csdn.net/u011466175/article/details/20712813