搜索
您的当前位置:首页正文

poj 2777 线段树(区间染色)

来源:欧得旅游网

题意:给一个固定长度为L的画板。有两个操作:1、C A B C:区间AB内涂上颜色C。2、P A B:查询区间AB内颜色种类数。

思路:区间显然要用线段树。颜色因为不超过30,所以可以用位运算。关键在于优化:每次更新到完整区间的时候标记一下,不更新到叶子节点,当后面更新或者查询需要用到比这个区间小的区间的时候再往下带。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 100005
struct node{
    int l,r,c;
    bool flag;//表示该区间的颜色是否更新到了叶子节点
}t[N<<2];
int n,num,q;
int mid(int a,int b){
    return (a+b)>>1;
}
void createTree(int root,int l,int r){
    t[root].l = l;
    t[root].r = r;
    t[root].flag = false;
    t[root].c = 1;
    if(l!=r){
        createTree(root*2, l, mid(l,r));
        createTree(root*2+1, mid(l,r)+1, r);
    }
}
void push(int root){
    t[root].flag = false;
    t[root*2].flag = t[root*2+1].flag = true;
    t[root*2].c = t[root*2+1].c = t[root].c;
}
void update(int root,int a,int b,int x){
    int mm = mid(t[root].l,t[root].r);
    if(t[root].l == a && t[root].r == b){//更新时候如果是整个区间那么标记,不再往下更新
        t[root].c = (1<<x);
        t[root].flag = true;
        return ;
    }
    if(t[root].flag)//如果需要,再往下带更新操作
        push(root);
    if(b <= mm)
        update(root*2,a,b,x);
    else if(a>mm)
        update(root*2+1, a, b, x);
    else{
        update(root*2, a, mm, x);
        update(root*2+1, mm+1, b, x);
    }
    t[root].c = t[root*2].c | t[root*2+1].c;
}
int query(int root,int a,int b){
    int mm = mid(t[root].l,t[root].r);
    if(t[root].l == a && t[root].r == b)
        return t[root].c;
    if(t[root].flag)
        push(root);
    if(b <= mm)
        return query(root*2, a, b);
    else if(a > mm)
        return query(root*2+1, a, b);
    else
        return query(root*2, a, mm) | query(root*2+1, mm+1, b);
}
int main(){
    int i,a,b,x,res;
    char cmd[5];
    scanf("%d %d %d",&n,&num,&q);
    createTree(1,1,n);
    while(q--){
        scanf("%s %d %d",cmd,&a,&b);
        if(a>b)
            swap(a,b);
        if(cmd[0] == 'C'){
            scanf("%d",&x);
            update(1,a,b,x-1);
        }else{
            res=0;
            x = query(1,a,b);
            for(i = 0;i<num;i++)
                if(x & (1<<i))
                    res++;
            printf("%d\n",res);
        }
    }
    return 0;
}


因篇幅问题不能全部显示,请点此查看更多更全内容

热门图文

Top