A Corrupt Mayor's Performance Art HDU - 5023

点击打开链接

血崩啊! 不看题的教训! 墙的颜色初始为2.. WA了一晚上

这里的状态压缩就是每段墙的所有颜色可以用一个数来表示

比如 olor 1就是2^1(0001) color 2就是2^2(0010) 而这两种颜色都有就是2^1+2^2(0011)

求两段墙合并后的颜色 可以通过位或实现

#include <bits/stdc++.h>
using namespace std;

struct node
{
    int l;
    int r;
    int val;
    int laz;
    int pre;
};

node tree[4000010];
int n,q;

void build(int l,int r,int cur);
void pushup(int cur);
void pushdown(int cur);
void update(int ll,int rr,int cur,int val);
int query(int ll,int rr,int cur);

int main()
{
    int bit[50],out[50];
    int val,sum;
    int i,j,l,r,cnt;
    char ch[2];
    while(scanf("%d%d",&n,&q)!=EOF)
    {
        if(n==0&&q==0) break;
        build(1,n,1);
        while(q--)
        {
            scanf("%s",ch);
            if(ch[0]=='P')
            {
                scanf("%d%d%d",&l,&r,&val);
                update(l,r,1,1<<val);
            }
            else
            {
                scanf("%d%d",&l,&r);
                sum=query(l,r,1);

                memset(bit,0,sizeof(bit));
                cnt=0;
                while(sum>0)
                {
                    bit[cnt++]=sum%2;
                    sum/=2;
                }
                cnt=0;
                for(i=0;i<=30;i++)
                {
                    if(bit[i]==1)
                    {
                        cnt++;
                        out[cnt]=i;
                    }
                }

                for(i=1;i<=cnt-1;i++)
                {
                    printf("%d ",out[i]);
                }
                printf("%d\n",out[i]);
            }
        }
    }
    return 0;
}

void build(int l,int r,int cur)
{
    int m;
    tree[cur].l=l;
    tree[cur].r=r;
    tree[cur].val=0;
    tree[cur].laz=0;
    tree[cur].pre=0;
    if(l==r)
    {
        tree[cur].val=4;
        return;
    }
    m=(l+r)/2;
    build(l,m,cur*2);
    build(m+1,r,cur*2+1);
    pushup(cur);
    return;
}

void pushup(int cur)
{
    tree[cur].val=tree[cur*2].val|tree[cur*2+1].val;
    return;
}

void pushdown(int cur)
{
    if(tree[cur].laz==1)
    {
        tree[cur*2].val=tree[cur].pre;
        tree[cur*2].laz=1;
        tree[cur*2].pre=tree[cur].pre;
        tree[cur*2+1].val=tree[cur].pre;
        tree[cur*2+1].laz=1;
        tree[cur*2+1].pre=tree[cur].pre;
        tree[cur].laz=0;
        tree[cur].pre=0;
    }
    return;
}

void update(int ll,int rr,int cur,int val)
{
    if(ll<=tree[cur].l&&tree[cur].r<=rr)
    {
        tree[cur].val=val;
        tree[cur].laz=1;
        tree[cur].pre=val;
        return;
    }
    if(tree[cur].l==tree[cur].r) return;
    pushdown(cur);
    if(ll<=tree[cur*2].r) update(ll,rr,cur*2,val);
    if(rr>=tree[cur*2+1].l) update(ll,rr,cur*2+1,val);
    pushup(cur);
    return;
}

int query(int ll,int rr,int cur)
{
    int ans,t1,t2;
    if(ll<=tree[cur].l&&tree[cur].r<=rr)
    {
        return tree[cur].val;
    }
    if(tree[cur].l==tree[cur].r) return 0;
    pushdown(cur);

    if(ll<=tree[cur*2].r) t1=query(ll,rr,cur*2);
    else t1=0;
    if(rr>=tree[cur*2+1].l) t2=query(ll,rr,cur*2+1);
    else t2=0;
    ans=t1|t2;
    return ans;
}