POJ 2777 Count Color

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 131072/65536K (Java/Other)

题意:“C”操作代表将[a,b]区间刷成颜色c
“p”操作询问区间[a,b]内颜色的数量

题解:

本题的突破口在这句「number of different colors T is very small. 」,题目给定范围是0-30,用二进制的话刚好在int范围内,既用一个30位的二进制数储存每个节点的颜色情况,有的为1,没有的为0,这种存储方式很像胜利大逃亡(续)中储存钥匙情况的模式,很经典的状态压缩方式。


每次只要处理一下PushUp的值就可以了,初始颜色为1,需要注意这句「A may be larger than B」,贡献了8次WA

//
//  main.cpp
//  专题9-线段树
//
//  Created by Edwin on 2019/3/2.
//  Copyright © 2019 Edwin. All rights reserved.
//
//#include<bits/stdc++.h>
#include<iostream>
#include<string.h>
#include<algorithm>
#include<string>
#include<math.h>
#include<stdio.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define maxn 100000+10
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define SZ(V) (int)V.size()
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define root 1,0,n-1
#define delf int m = (r + l) / 2
using namespace std;
int lazy[maxn<<2];
int Hash[maxn<<2];//线段树,记录每个树的颜色情况,30种颜色用位运算记录
void init(){
    mst(lazy,0);
    mst(Hash,1);
}
void PushUp(int rt){
    Hash[rt]=Hash[rt<<1]|Hash[rt<<1|1];
}
void PushDown(int rt){
    if(lazy[rt]){
        lazy[rt<<1]=lazy[rt];
        lazy[rt<<1|1]=lazy[rt];
        Hash[rt<<1] = lazy[rt];
        Hash[rt<<1|1] = lazy[rt];
        lazy[rt] = 0;
    }
}
void build(int l,int r,int rt){
    if (l==r){
        Hash[rt]=1;
        return;
    }
    delf;
    build(lson);
    build(rson);
    PushUp(rt);
}
void update(int L,int R,int c,int l,int r,int rt){//区间更新
    if(L > r || R < l )
        return ;
    if (L<=l&&r<=R){
        Hash[rt]=1<<(c-1);
        lazy[rt]=1<<(c-1);
        return;
    }
    delf;
    PushDown(rt);
    if (L<=m) update(L,R,c,lson);
    if (R>m) update(L,R,c,rson);
    PushUp(rt);
}
ll query(int ql,int qr,int l,int r,int rt){
    if(ql > qr) return 0;
    if(ql > r || qr < l) return 0;
    if(ql <= l && r <= qr){
        return Hash[rt];
    }
    delf;
    PushDown(rt);
    return query(ql,qr,lson)|query(ql,qr,rson);
}
int countbits(ll value){
    int count = 0;
    while(value){
        if(value & 1)
            count++ ;
        value >>= 1 ;
    }
    return count;
}
int main(){
    int l,t,q;
    scanf("%d %d %d",&l,&t,&q);
    init();
    build(1,l,1);
    while(q--){
        char str[2];
        scanf("%s",str);
        if(str[0]=='C'){
            int ql,qr,c;
            scanf("%d%d%d",&ql,&qr,&c);
            if(ql > qr)
                swap(ql,qr);
            update(ql,qr,c,1,l,1);
        }
        else{
            int ql,qr;
            sc2(ql,qr);
            if(ql > qr)
                swap(ql,qr);
            printf("%d\n",countbits(query(ql,qr,1,l,1)));
        }
        
    }
    return 0;
}

 

发表评论,支持MarkDown语法