線分ツリー-POJ 2777
これは統計的な問題であるが、2つの操作が与えられ、C A B color:区間[A,B]に色colorを塗り、P A Bは区間[A,B]の色の数を統計して印刷し、図色の種類は30種類を超えず、区間の長さは最大100000に達し、与えられた操作回数は最大100000に達する.
これは古典的な線分ツリーのテーマで、色の数は最大30種類しかないため、32ビット整形の各ビットで対応する色を表すことができ、集約の操作を容易にすることができます.
これは古典的な線分ツリーのテーマで、色の数は最大30種類しかないため、32ビット整形の各ビットで対応する色を表すことができ、集約の操作を容易にすることができます.
#include<cstdio>
#include<cstring>
#include<iostream>
#define N 100100
using namespace std;
int l,t,o;
long long int color[N<<2];
int count(int k)// 1
{
int ans=0;
while(k>0)
{
ans++;
k-=(k&(-k));// K 1
//
}
return ans;
}
void update(int rt,int ld,int rd,int s,int e,long long int c)
{
if(s<=ld && rd<=e) {
color[rt]=c;
return ;
}
int mid=(ld+rd)>>1;
int cnt = count(color[rt]);
if(cnt==1) {color[rt<<1]=color[rt];color[rt<<1|1]=color[rt];}
if(e<=mid) update(rt<<1,ld,mid,s,e,c);
else if(s>mid) update(rt<<1|1,mid+1,rd,s,e,c);
else {
update(rt<<1,ld,mid,s,mid,c);
update(rt<<1|1,mid+1,rd,mid+1,e,c);
}
color[rt]=color[rt<<1]|color[rt<<1|1];
}
int query(int rt,int ld,int rd,int s,int e)
{
if(s<=ld && rd<=e) return color[rt];
int mid=(ld+rd)>>1;
int cnt=count(color[rt]);
if(cnt==1) return color[rt];
if(e<=mid) return query(rt<<1,ld,mid,s,e);
else if(s>mid) return query(rt<<1|1,mid+1,rd,s,e);
else {
int c1=query(rt<<1,ld,mid,s,mid);
int c2=query(rt<<1|1,mid+1,rd,mid+1,e);
return c1|c2;
}
}
void getline(char *s)
{
char ch;
int i=0;
while(true) {
scanf("%c",&ch);
s[i++]=ch;
if(ch=='
') break;
}
s[i]='\0';
}
int main()
{
while(scanf("%d%d%d",&l,&t,&o)!=EOF){
char str[20],ch;
for(int i=0;i<4*N;i++) color[i]=1;
scanf("%c",&ch);
for(int i=0; i<o; i++) {
getline(str);
int a,b,c;
sscanf(str,"%c%d%d",&ch,&a,&b);
int temp = a;
if(a>b) {
a=b;
b=temp;
}
if (ch=='C') {
sscanf(str,"%c%d%d%d",&ch,&a,&b,&c);
update(1,1,l,a,b,1<<(c-1));
}
if(ch=='P') printf("%d
", count(query(1,1,l,a,b)));
}
}
return 0;
}