題目大意：給出了兩個操作：1、C A B D，將區間[A,B]賦值為D；2、P A B，輸出區間[A,B]中有多少個不同的數。
一上午時間，極度郁悶地完成了這道題，原因是看漏了一個條件：At the beginning,the board was painted in color 1.結果我卻認為一開始是沒有顏色的……
數據規模L=100000，肯定需要一個O(nlogn)的算法，于是需要在O(logn)內完成插入和查詢操作，考慮線段樹。
最多只有30種顏色，可以用long整數表示一個區間的顏色：二進制。用按位或運算就可以實現集合的合并。
以下是我的代碼：
#include<stdio.h>
const long maxL=100007;
typedef struct
{
long a,b;
unsigned long color;
long left,right;
}node;
long L,T,O,tot;
node tree[maxL*7];
void swap(long &a,long &b)
{
long t=a;a=b;b=t;
}
long kind(unsigned long color)
{// How many colors in Color
long re=0;
for(long i=1;i<=T;i++)
if(color&(1<<i))
re++;
return re;
}
void build(long begin,long end)
{// Build A Segment Tree
long now,mid=(begin+end)>>1;
tot++;now=tot;
tree[now].a=begin;tree[now].b=end;tree[now].color=2;
if(begin<end)
{
tree[now].left=tot+1;build(begin,mid);
tree[now].right=tot+1;build(mid+1,end);
}
}
void insert(long x,long y,long c,long node)
{// Insert
long a=tree[node].a,b=tree[node].b,t=(a+b)>>1;
if(x<=a&&b<=y)
tree[node].color=(1<<c);
else
{
//------
if(kind(tree[node].color)<=1)
tree[tree[node].left].color=tree[tree[node].right].color=tree[node].color;
//------
if(t>=x)
insert(x,y,c,tree[node].left);
if(t+1<=y)
insert(x,y,c,tree[node].right);
tree[node].color=tree[tree[node].left].color|tree[tree[node].right].color;
}
}
unsigned long getcol(long x,long y,long node)
{// return color(s) of [x,y]
long l=0,r=0,a=tree[node].a,b=tree[node].b,t=(a+b)>>1;
if(kind(tree[node].color)<=1)
return tree[node].color;
if(x<=a&&b<=y)
return tree[node].color;
if(t>=x)
l=getcol(x,y,tree[node].left);
if(t+1<=y)
r=getcol(x,y,tree[node].right);
return l|r;
}
int main()
{
scanf("%ld%ld%ld",&L,&T,&O);getchar();
tot=0;
build(1,L);
for(long i=1;i<=O;i++)
{
char cmd;
long a,b,c;
cmd=getchar();
switch(cmd)
{
case 'C':
scanf("%ld%ld%ld",&a,&b,&c);getchar();
if(a>b) swap(a,b);
insert(a,b,c,1);
break;
case 'P':
scanf("%ld%ld",&a,&b);getchar();
if(a>b) swap(a,b);
printf("%ld\n",kind(getcol(a,b,1)));
break;
}
}
return 0;
}
posted on 2010-02-18 13:38
lee1r 閱讀(1072)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：數據結構