Wednesday, November 16, 2011
线段树，WA了无数次，又TLE了两次。WA的原因是solve函数写错，TLE的原因是solve写的太挫了。。。。
题意：[1,L]的染色板，初始化都是1号色，[1,T]种不同的颜色，可进行O次操作。
操作有两种：
C A B C 将染色板A到B所有的格子染成C号色
P A B 询问染色板A到B中颜色的种数
思路：很简单的线段树，更新处理的时候更新到树根会超时，应该成段更新，询问的时候没处理好也可能会超时。
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN=100003;
int flag[33],color[MAXN];
typedef struct
{
int left,right,col;
}line;
line tree[4*MAXN];
int sum;
void Create(int l,int r,int root) //建树
{
tree[root].left=l;
tree[root].right=r;
tree[root].col=1;
if(l==r) return;
int mid=(l+r)>>1;
Create(l,mid,root<<1);
Create(mid+1,r,(root<<1)+1);
}
void Updata(int l,int r,int colo,int root) //更新染色板
{
if(l<=tree[root].left&&tree[root].right<=r)
{
tree[root].col=colo;
return;
}
if(tree[root].col==colo) return;
if(tree[root].left==tree[root].right) return;
if(tree[root].col>=0) //如果这一段的颜色超过1种，则向下更新之前的颜色，并将本段颜色赋值-1
{
tree[root<<1].col=tree[root].col;
tree[(root<<1)+1].col=tree[root].col;
tree[root].col=-1;
}
int mid=(tree[root].left+tree[root].right)>>1;
if(l>mid) Updata(l,r,colo,(root<<1)+1);
else if(r<=mid) Updata(l,r,colo,root<<1);
else
{
Updata(l,mid,colo,root<<1);
Updata(mid+1,r,colo,(root<<1)+1);
}
}
void solve(int l,int r,int root) //询问
{
if(tree[root].col>=0) //如果父节点有单一的颜色，就直接更新，不需要找到子节点更新
{
flag[tree[root].col]=1;//统计哪些颜色出现过
return;
}
if(tree[root].left==tree[root].right) return;
int mid=(tree[root].left+tree[root].right)>>1;
if(l>mid) solve(l,r,(root<<1)+1);
else if(r<=mid) solve(l,r,root<<1);
else
{
solve(l,mid,root<<1);
solve(mid+1,r,(root<<1)+1);
}
}
int main()
{
//freopen("input","r",stdin);
int n,t,o;
while(scanf("%d %d %d",&n,&t,&o)!=EOF)
{
memset(color,0,sizeof(color));
Create(1,n,1);
int tl,tr,tc;
char str[2];
for(int i=0;i<o;i++)
{
scanf("%s",str);
if(str[0]=='C')
{
scanf("%d %d %d",&tl,&tr,&tc);
if(tl>tr)
{
int temp=tl;
tl=tr;
tr=temp;
}
Updata(tl,tr,tc,1);
}
else if(str[0]=='P')
{
memset(flag,0,sizeof(flag));
scanf("%d %d",&tl,&tr);
if(tl>tr)
{
int temp=tl;
tl=tr;
tr=temp;
}
sum=0;
solve(tl,tr,1);
for(int i=1;i<=t;i++)
if(flag[i]) sum++;
printf("%d\n",sum);
}
}
}
return 0;
}