p2777.cpp

大概POJ上50道比较难的题的代码

#include <iostream>
using namespace std;
const int MAXN = 300000;
int f[MAXN];
bool pure[MAXN];
int count(int x){
    int res(0);
    while(x){
        res += (x & 1);
        x >>= 1;
    }
    return res;
}
void change(int b,int e,int x,int y,int c,int v){
    if(f[v] == 1 << c-1) return;
    if(b == x && e == y){
        f[v] = 1 << c-1;
        pure[v] = true;
        return;
    }
    if(pure[v]){
        f[v<<1] = f[(v<<1)+1] = f[v];
        pure[v] = false;
    }
    int mid = b+e >> 1;
    if(y <= mid) change(b,mid,x,y,c,v<<1);
    else if(x > mid) change(mid+1,e,x,y,c,(v<<1)+1);
    else{
        change(b,mid,x,mid,c,v<<1);
        change(mid+1,e,mid+1,y,c,(v<<1)+1);
    }
    f[v] = f[v<<1] | f[(v<<1)+1];
    if(f[v] & (f[v]-1) == 0) pure[v] = true;
}
int query(int b,int e,int x,int y,int v){
    int mid = b+e >> 1;
    if(pure[v]) return f[v];
    if(b == x && e == y) return f[v];
    if(y <= mid) return query(b,mid,x,y,v<<1);
    else if(x > mid) return query(mid + 1,e,x,y,(v<<1)+1);
    else return query(b,mid,x,mid,v<<1) | query(mid + 1,e,mid + 1,y,(v<<1)+1);
}
void out(int a,int b,int v){
    printf("%d %d %d \n",a,b,f[v]);
    if(a==b)return ;
    out(a,a+b>>1,(v<<1));
    out((a+b>>1)+1,b,(v<<1)+1);
}
int main(){
    char ch;
    int L,t,o,a,b,c;
    for(int i = 0;i < MAXN;++i) f[i] = 1;
    memset(pure,false,sizeof(pure));
    cin >> L >> t >> o;
    for(int i = 0;i < o;++i){
        cin >> ch;
        if(ch == 'C'){
            scanf("%d%d%d",&a,&b,&c);
            if(a > b) swap(a,b);            
            change(1,L,a,b,c,1);
//            out(1,L,1);
        }
        else{
            scanf("%d%d",&a,&b);
            if(a > b) swap(a,b);
            printf("%d\n",count(query(1,L,a,b,1)));
        }
    }
}