题目大意：要求完成以下两个操作：1.将一个区间刷上一种颜色2.询问一段区间上有多少种颜色
思路：这两个操作线段树都可以很迅速的完成，具体做法是：线段树上每个节点存这个线段上的颜色数量，由于颜色数很少，因此可以用二进制存颜色，如果二进制的第N位是1，则该区间存在颜色N，因此一个节点等于其两个子节点颜色的或。最后一个问题就是修改操作是对区间修改，因此需要用lazy_tag的思想（虽然这里不完全是），不然一个一个插节点会TLE
#include<cstdio>
#include<string.h>
#include<iostream>
using namespace std;
int tree[500000]={0};
bool lazy[500000]={0};
void swap(int &x,int &y){int temp=x;x=y;y=temp;}
int search(int node,int l,int r,int lq,int rq)
{
int mid=(l+r)>>1,temp=0;
if (lazy[node]==true){return tree[node];}
if (lq<=l && r<=rq){return tree[node];}
else
{
if (lazy[node]==1){lazy[node<<1]=1;tree[node<<1]=tree[node];
tree[(node<<1)+1]=tree[node];lazy[(node<<1)+1]=1;}
if (lq<=mid)temp=search(node<<1,l,mid,lq,rq);
if (mid<rq)temp=temp | search((node<<1)+1,mid+1,r,lq,rq);
}
return temp;
}
void insert(int node,int l,int r,int lq,int rq,int color)
{
int mid=(l+r)>>1;
if (lq<=l && r<=rq){tree[node]=1<<(color-1);lazy[node]=true;return;}
else
{
if (lazy[node]==1)
{
lazy[node]=0;lazy[node<<1]=1;
tree[node<<1]=tree[node];tree[(node<<1)+1]=tree[node];
lazy[(node<<1)+1]=1;
}
if (lq<=mid)insert(node<<1,l,mid,lq,rq,color);
if (rq>mid)insert((node<<1)+1,mid+1,r,lq,rq,color);
}
tree[node]=tree[node<<1] | tree[(node<<1)+1];
}
int f(int u)
{
int t=0;while(u!=0){if ((u & 1)==1)t++;u>>=1;}
return t;
}
int main()
{
int t,o,l,left,right,color;
char ch[2];
scanf("%d%d%d",&l,&t,&o);
for(int i=1;i<=4*l;i++)tree[i]=1;
for(int v=1;v<=o;v++)
{
scanf("%s",ch);
if (ch[0]==‘C‘)
{
scanf("%d%d%d",&left,&right,&color);
if (right<left)swap(right,left);
insert(1,1,l,left,right,color);
}
else
{
scanf("%d%d",&left,&right);
if (right<left)swap(right,left);
int u=search(1,1,l,left,right);
printf("%d\n",f(u));
}
}
return 0;
}
原文：http://www.cnblogs.com/philippica/p/4006986.html