http://poj.org/problem?id=2777
前几天看到一个大神说，要搞，就搞专题或者套题，我觉得现在这么菜的我，还是搞搞专题吧。
一道比较裸也比较基础的线段树的题目。
题意：就是有一段木头，可以对这个木头进行两种操作，一是进行涂色，而是进行查询，如果一个木头之前涂过色，那么之后涂色的话，会对之前的进行覆盖。
很明显的一个线段树的题目，不用线段树肯定超时的。
#include <stdio.h>
#include <string.h>
#define maxn 1000005 struct note{
int l,r;
int col;
}Tegtree[ *maxn ];
bool mark[]; void bulid(int root,int st,int en)
{
Tegtree[ root ].l = st;
Tegtree[ root ].r = en;
if(st == en) return ;
int mid = ( Tegtree[ root ].l + Tegtree[ root ].r )>>;
bulid( root << , st , mid );
bulid( (root << ) + , mid + , en );
} void Update(int root,int x,int y,int colc)
{
if(Tegtree[ root ].l >= x && Tegtree[ root ].r <=y )
{
Tegtree[ root ].col = colc;
return ;
} else
{
if(Tegtree[root].col > ) //进行延迟标记。
{
Tegtree[ root << ].col = Tegtree[root].col;
Tegtree[( root << ) + ].col = Tegtree[root].col;
Tegtree[root].col = ;
}
int mid = (Tegtree[ root ].l + Tegtree[ root ].r ) >> ;
if(x>mid){
Update((root<<)+,x,y,colc);
}else if(y<=mid){
Update(root<<,x,y,colc);
}else {
Update(root<<,x,mid,colc);
Update((root<<)+,mid+,y,colc);
}
}
}
void Find(int root,int x,int y)
{
if(Tegtree[root].col > )
{
mark[Tegtree[root].col] = true;
}else{
int mid = (Tegtree[ root ].l + Tegtree[ root ].r ) >> ;
if(x>mid){
Find((root<<)+,x,y);
}else if(y<=mid){
Find(root<<,x,y);
}else {
Find(root<<,x,mid);
Find((root<<)+,mid+,y);
}
}
} int main()
{
// freopen("in.txt","r",stdin);
int l,t,o,a,b,c;
char tmp[];
while(scanf("%d%d%d",&l,&t,&o)!=EOF)
{
Tegtree[].col = ;
bulid(,,l);
while(o--)
{ scanf("%s",tmp);
// printf("%s\n",tmp);
if(tmp[]=='C')
{
scanf("%d%d%d",&a,&b,&c);
getchar();
Update(,a,b,c);
}
else if(tmp[]=='P')
{
scanf("%d%d",&a,&b);
getchar();
memset(mark,false,sizeof(mark));
Find(,a,b);
int ans = ;
for(int i = ; i <= ; i++)
if(mark[i]) ans++;
printf("%d\n",ans);
}
}
}
return ;
}