首页 > 代码库 > poj 2777

poj 2777

2024-07-22 20:19:30   220人阅读

题意：两个操作：c l r x   l到r之间的颜色变成x

                      q l r      询问l到r有多少种颜色

思路：记一个整数表示哪种颜色是否取了

        这里真的是煞笔了，看到这一题第一直觉是异或，但是A^A=0，相同的肿么办..然后搜题解....反应了一个下午，发现有按位或这样神气的存在

        1|1=1
        1|0=1
        0|1=1
        0|0=0
代码
#include "stdio.h"#include "string.h"#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#include "algorithm"#define MAX 100010using namespace std;int sum[MAX<<2],col[MAX<<2];void pushup(int rt){    sum[rt]=(sum[rt<<1]|sum[rt<<1|1]);}void pushdown(int rt){    if(col[rt])    {        col[rt<<1]=col[rt<<1|1]=col[rt];        sum[rt<<1]=sum[rt<<1|1]=1<<(col[rt]-1);        col[rt]=0;    }}void build(int l,int r,int rt){    col[rt]=0;    if(l==r)    {        sum[rt]=1;        return;    }    int m=(l+r)>>1;    build(lson);    build(rson);    pushup(rt);}void update(int L,int R,int c,int l,int r,int rt){    if(l>=L&&r<=R)    {          col[rt]=c;          sum[rt]=1<<(c-1);          return;    }    pushdown(rt);    int m=(l+r)>>1;    if(L<=m)        update(L,R,c,lson);    if(R>m)        update(L,R,c,rson);    pushup(rt);}int query(int L,int R,int l,int r,int rt){    if(l>=L&&r<=R)    {          return sum[rt];    }    pushdown(rt);    int ans=0;    int m=(l+r)>>1;    if(L<=m)          ans=(ans|query(L,R,lson));    if(R>m)          ans=(ans|query(L,R,rson));    return ans;}int main(){    int n,l,r,col,x;    int q;    char s[10];    while(scanf("%d%d%d",&n,&col,&q)==3)    {        build(1,n,1);        while(q--)        {            scanf("%s",s);            if(s[0]==‘C‘)            {                scanf("%d%d%d",&l,&r,&x);                if(l>r)                    l^=r^=l^=r;                update(l,r,x,1,n,1);            }            else           {               scanf("%d%d",&l,&r);               if(l>r)                    l^=r^=l^=r;               int temp=query(l,r,1,n,1);               int ans=0;               while(temp)               {                   if(temp&1)                        ans++;                   temp/=2;               }               printf("%d\n",ans);           }        }    }    return 0;}
View Code

 

poj 2777


联系
我们