POJ 2777 Count Color【线段树】

题目大意：要求完成以下两个操作：1.将一个区间刷上一种颜色2.询问一段区间上有多少种颜色

思路：这两个操作线段树都可以很迅速的完成，具体做法是：线段树上每个节点存这个线段上的颜色数量，由于颜色数很少，因此可以用二进制存颜色，如果二进制的第N位是1，则该区间存在颜色N，因此一个节点等于其两个子节点颜色的或。最后一个问题就是修改操作是对区间修改，因此需要用lazy_tag的思想（虽然这里不完全是），不然一个一个插节点会TLE

#include<cstdio>

#include<string.h>

#include<iostream>

using namespace std;

int tree[500000]={0};

bool lazy[500000]={0};

void swap(int &x,int &y){int temp=x;x=y;y=temp;}

int search(int node,int l,int r,int lq,int rq)

{

int mid=(l+r)>>1,temp=0;

if (lazy[node]==true){return tree[node];}

if (lq<=l && r<=rq){return tree[node];}

else

{

if (lazy[node]==1){lazy[node<<1]=1;tree[node<<1]=tree[node];

tree[(node<<1)+1]=tree[node];lazy[(node<<1)+1]=1;}

if (lq<=mid)temp=search(node<<1,l,mid,lq,rq);

if (mid<rq)temp=temp | search((node<<1)+1,mid+1,r,lq,rq);

}

return temp;

}

void insert(int node,int l,int r,int lq,int rq,int color)

{

int mid=(l+r)>>1;

if (lq<=l && r<=rq){tree[node]=1<<(color-1);lazy[node]=true;return;}

else

{

if (lazy[node]==1)

{

lazy[node]=0;lazy[node<<1]=1;

tree[node<<1]=tree[node];tree[(node<<1)+1]=tree[node];

lazy[(node<<1)+1]=1;

}

if (lq<=mid)insert(node<<1,l,mid,lq,rq,color);

if (rq>mid)insert((node<<1)+1,mid+1,r,lq,rq,color);

}

tree[node]=tree[node<<1] | tree[(node<<1)+1];

}

int f(int u)

{

int t=0;while(u!=0){if ((u & 1)==1)t++;u>>=1;}

return t;

}

int main()

{

int t,o,l,left,right,color;

char ch[2];

scanf("%d%d%d",&l,&t,&o);

for(int i=1;i<=4*l;i++)tree[i]=1;

for(int v=1;v<=o;v++)

{

scanf("%s",ch);

if (ch[0]=='C')

{

scanf("%d%d%d",&left,&right,&color);

if (right<left)swap(right,left);

insert(1,1,l,left,right,color);

}

else

{

scanf("%d%d",&left,&right);

if (right<left)swap(right,left);

int u=search(1,1,l,left,right);

printf("%d\n",f(u));

}

return 0;

}

巴特西

POJ 2777 Count Color【线段树】

最新文章

热门文章