题目大意：给出了两个操作：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 阅读(1066)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：数据结构