1. 题目

传送门= ̄ω ̄=
题意:一条很长(L)的画板(初始颜色为 1),有 T 种颜色,O 个操作;每次操作将一个区间刷成一种颜色,或者查询一个区间内所含的颜色数。

其中 L<=1e5,T<=30,O<=1e5

TMD有多组数据

2. 题解

显然线段树
然后因为颜色数不大于 30,可以用位运算(int 就够了)
把一个区间覆盖为颜色 i 就让这个区间的值变为 1<<i

然后区间求和就和普通线段树一样,这不过这里是求区间的或和的二进制下 1 的位数

至于求一个数的二进制下 1 的位数,用 lower_bound 函数可以快速求得。

用指针线段树会TLE,因为要清空树,耗时间,而且动态申请内存也慢。

代码:

#include <cstdio>
#include <algorithm>
#include <cctype>
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
using namespace std;
struct N{int l,r,d,f;N(){l=r=d=f=0;}}e[500000];
void update(int a){e[a].d=(e[LS(a)].d|e[RS(a)].d);}
void pdown(int a)
{
    e[LS(a)].f=e[a].f,e[LS(a)].d=(1<<(e[a].f));
    e[RS(a)].f=e[a].f,e[RS(a)].d=(1<<(e[a].f));
    e[a].f=0;
}
void build(int l,int r,int a)
{
    e[a].l=l,e[a].r=r,e[a].d=2;
    if(l<r)build(l,(l+r)>>1,LS(a)),build(((l+r)>>1)+1,r,RS(a));
}
int query(int l,int r,int a)
{
    if(l<=e[a].l&&e[a].r<=r)return e[a].d;
    if(e[a].f)pdown(a);
    int tot=0;
    if(l<=((e[a].l+e[a].r)>>1))tot|=query(l,r,LS(a));
    if(r>((e[a].l+e[a].r)>>1))tot|=query(l,r,RS(a));
    return tot;
}
void change(int l,int r,int k,int a)
{
    if(l<=e[a].l&&e[a].r<=r){e[a].d=(1<<k),e[a].f=k;return;}
    if(e[a].f)pdown(a);
    if(l<=((e[a].l+e[a].r)>>1))change(l,r,k,LS(a));
    if(r>((e[a].l+e[a].r)>>1))change(l,r,k,RS(a));
    update(a);
}
int cnt(int a){int tot=0;while(a)tot++,a-=(a&-a);return tot;}
int n,t,o;
int main()
{
    while(~scanf("%d%d%d",&n,&t,&o))
    {
        build(1,n,1);
        for(int i=1,a,b,c,d;i<=o;i++)
        {
            do a=getchar();while(!isalpha(a));
            scanf("%d%d",&b,&c);
            if(b>c)swap(b,c);
            if(a>'C')printf("%d\n",cnt(query(b,c,1)));
            else scanf("%d",&d),change(b,c,d,1);
        }
    }
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

tense · 2017年7月12日 9:02 上午

这是 poj2777!!!

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注