hdu 5023 （线段树 ）

                             这道题当时没有做出来，状态不会保存。原来可已用二进制保存状态，做的题太少，暴漏的问题太多了；这么简单的东西，，，，，也不会保存

                            这道题就是每一次维护区间的和，也就是把它的30种颜色用二进制保存下来。也就1<<30   可以用long  long  保存下来

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define maxx  1111111
#define lson L,m,rt<<1
#define rson m+1,R,rt<<1|1
typedef long long ll;
int cnt;
ll add[maxx<<2];
int ans[50];
ll sum[maxx<<2];
int n,m;

void pushup(int rt){
   sum[rt]=sum[rt<<1]|sum[rt<<1|1];
}

void pushdown(int rt){
     if(add[rt]){
         add[rt<<1]=add[rt];
         add[rt<<1|1]=add[rt];
         sum[rt<<1]=add[rt];
         sum[rt<<1|1]=add[rt];
         add[rt]=0;
     }
}

void build(int L,int R,int rt){
     add[rt]=0;
     if(L==R){
        sum[rt]=2;（颜色2相当于1<<1，那么颜色1就1<<0）
        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){
        add[rt]=1<<(c-1);
        sum[rt]=1<<(c-1);
        return ;
     }
     pushdown(rt);
     int m=(L+R)>>1;
     if(l<=m) update(l,r,c,lson);
     if(m<r)  update(l,r,c,rson);
     pushup(rt);
}

ll query(int l,int r,int L,int R,int rt){
      ll ret=0;
      if(l<=L&&r>=R){
       return sum[rt];
      }
      pushdown(rt);
      int m=(L+R)>>1;
      if(l<=m) ret|=query(l,r,lson);
      if(m<r)  ret|=query(l,r,rson);
      return ret;
}

int main(){
      while(scanf("%d%d",&n,&m)!=EOF){
      if(n==0&&m==0) break;
      build(1,n,1);
      while(m--){
        char op[2];
        scanf("%s",op);
        int a,b,c;
        if(op[0]=='P'){
            scanf("%d%d%d",&a,&b,&c);
            update(a,b,c,1,n,1);
        }
        else {
            memset(ans,0,sizeof(ans));
            cnt=0;
            scanf("%d%d",&a,&b);
            ll r=query(a,b,1,n,1);
            for(int i=0;i<30;i++){
                if(r&(1<<i)){
                    ans[cnt++]=i+1;
                }
            }
            int flag =0;
            for(int i=0;i<cnt;i++){
                if(flag){
                    printf(" %d",ans[i]);
                }
                else {
                    printf("%d",ans[i]);
                    flag =1 ;
                }
            }
            puts("");
        }
      }
}
}

hdu 5023 （线段树 ）

原文：http://blog.csdn.net/u013076044/article/details/41808535