POJ 2777線分樹+lazy思想+染色問題
ソース:http://poj.org/problem?id=2777
标题:1区間あって、せいぜい30色.2つの操作があり、1つは、ある区間セグメントに対してある色を染めることであり、1つは、その区間に何種類の異なる色があるかを尋ねることである.
構想:セグメントツリーの良い問題、セグメントツリー+lazy思想の経典応用.そしてビット演算と結びついています.色の数が少なく、親ノードの色はちょうど2つのサブノードの色のビット単位またはであるため、ビット演算を使用できます.最後の1つの数が異なる色の数です.
acコード:
标题:1区間あって、せいぜい30色.2つの操作があり、1つは、ある区間セグメントに対してある色を染めることであり、1つは、その区間に何種類の異なる色があるかを尋ねることである.
構想:セグメントツリーの良い問題、セグメントツリー+lazy思想の経典応用.そしてビット演算と結びついています.色の数が少なく、親ノードの色はちょうど2つのサブノードの色のビット単位またはであるため、ビット演算を使用できます.最後の1つの数が異なる色の数です.
acコード:
#include <iostream>
#include <cstdio>
using namespace std;
const int N=100010;
struct tree{
int left,right,numcol;
bool cover;
}tt[N*4];
int len,numcolour,numop,x,y;
void build_tree(int lp,int rp,int pos){
tt[pos].left=lp;
tt[pos].right=rp;
tt[pos].numcol=(1<<1);
tt[pos].cover=true;
if(lp==rp)return;
int mid=(lp+rp)/2;
build_tree(lp,mid,pos*2);
build_tree(mid+1,rp,pos*2+1);
}
void add(int lp,int rp,int id,int pos){
if(lp<=tt[pos].left&&rp>=tt[pos].right){
tt[pos].cover=true;
tt[pos].numcol=(1<<id);
return;
}
if(tt[pos].cover){
tt[pos*2].cover=true;
tt[pos*2+1].cover=true;
tt[pos*2].numcol=tt[pos].numcol;
tt[pos*2+1].numcol=tt[pos].numcol;
tt[pos].cover=false;
}
int mid=(tt[pos].left+tt[pos].right)/2;
if(lp<=mid)
add(lp,rp,id,pos*2);
if(rp>mid)
add(lp,rp,id,pos*2+1);
tt[pos].numcol=tt[pos*2].numcol|tt[pos*2+1].numcol;
}
int query(int lp,int rp,int pos){
if(tt[pos].left==lp&&tt[pos].right==rp){
return tt[pos].numcol;
}
if(tt[pos].cover){
tt[2*pos].cover=true;
tt[2*pos+1].cover=true;
tt[2*pos].numcol=tt[pos].numcol;
tt[2*pos+1].numcol=tt[pos].numcol;
tt[pos].cover=false;
}
int mid=(tt[pos].left+tt[pos].right)/2;
if(lp>mid)
return query(lp,rp,pos*2+1);
else if(rp<=mid)
return query(lp,rp,pos*2);
else
return query(lp,mid,pos*2)|query(mid+1,rp,pos*2+1);
}
int fenjie(int x){
int ans=0;
while(x){
if(x%2)
ans++;
x/=2;
}
return ans;
}
int main(){
//freopen("1.txt","r",stdin);
while(~scanf("%d%d%d",&len,&numcolour,&numop)){
build_tree(1,len,1);
char ss[2];
int id;
while(numop--){
scanf("%s",ss);
if(ss[0]=='C'){
scanf("%d%d%d",&x,&y,&id);
if(x>y)
swap(x,y);
add(x,y,id,1);
}
else{
scanf("%d%d",&x,&y);
if(x>y)
swap(x,y);
int sum=query(x,y,1);
int total=fenjie(sum);
printf("%d
",total);
}
}
}
return 0;
}