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;
}