题目大意:有一长为L的木板,将其分为等长的L段,从左到右编号为1~L.现将L段木板着色
1. 输入"C A B C" 是将A到B这一段着成C这种颜色.
2. 输入"P A B" 是要你计算从A到B这一段有多少种不同的颜色.
我们的任务就是计算从A到B有多少种不同的颜色.(题中1<=L<=100000最多有T(30)种不同的颜色,有O(100000)个操作)
解法是用线段树
#include "iostream"
#define Max 100000
using namespace std;
bool record[35];//用来记录有多少种不同的颜色
struct node_tree
{
int l,r,colr;
};
node_tree tre[Max*3];
void build(int i,int l,int r)//建树
{
tre[i].l=l;
tre[i].r=r;
tre[i].colr=1;//初始化颜色
if(l<r)
{
int mid=(r+l)>>1;
build(2*i,l,mid);//左子树
build(2*i+1,mid+1,r);//右子树
}
}
void insert(int i,int l,int r,int colr)//插入函数(在这里是着色)
{
if (tre[i].l>=l&&tre[i].r<=r)
{
tre[i].colr=colr;
return ;
}
if (tre[i].l<tre[i].r)
{
int mid=(tre[i].l+tre[i].r)>>1;
if (tre[i].colr>0)
{
tre[2*i].colr=tre[i].colr;
tre[2*i+1].colr=tre[i].colr;
}
tre[i].colr=-1;
if (r<=mid)//插入左子树
{
insert(2*i,l,r,colr);
}
else if(l>mid)//插入右子树
{
insert(2*i+1,l,r,colr);
}
else
{
insert(2*i,l,mid,colr);
insert(2*i+1,mid+1,r,colr);
}
}
}
void cot(int i,int l,int r)//计算有多少种颜色
{
if (tre[i].colr>0)
{
record[tre[i].colr]=true;
return ;
}
if (tre[i].l<tre[i].r)
{
int mid=(tre[i].l+tre[i].r)>>1;
if(r<=mid)
cot(2*i,l,r);
else if(l>mid)
cot(2*i+1,l,r);
else
{
cot(2*i,l,mid);
cot(2*i+1,mid+1,r);
}
}
}
int main()
{
int i,j;
int l,t,o;
char ch;
int a,b,c;
cin>>l>>t>>o;
build(1,1,l);
for (i=0;i<o;i++)
{
cin>>ch;
if (ch=='C')
{
scanf("%d%d%d",&a,&b,&c);
if(a<=b)
insert(1,a,b,c);
else
insert(1,b,a,c);
}
else
{
scanf("%d%d",&a,&b);
memset(record,false,sizeof(record));
if(a<=b)
cot(1,a,b);
else
cot(1,b,a);
int ans=0;
for (j=1;j<=t;j++)
{
if (record[j])
{
ans++;
}
}
printf("%d\n",ans);
}
}
return 0;
}