博客

给定一个长度为n(n <= 100000)的木板，支持两种操作：

1、P a b c       将[a, b]区间段染色成c；

2、Q a b         询问[a, b]区间内有多少种颜色；

保证染色的颜色数少于30种。

思路：

因为颜色种类少于30，因此可以用int型整数来表示所有颜色，每一个比特代表一种颜色，颜色从0开始。

#include <iostream>
using namespace std;

const int MAXN = 1e5;

struct Node
{
    int color;
    int lazy;
};

Node t[MAXN << 2];

void build(int rt, int left, int right)
{
    t[rt].color = 0;
    t[rt].lazy = 0;

    if (left == right)
    {
        return;
    }
    
    int mid = left + (right - left) / 2;
    build(rt << 1, left, mid);
    build(rt << 1 | 1, mid + 1, right);
}

void pushDown(int rt)
{
    if (t[rt].lazy)
    {
        t[rt << 1].lazy |= t[rt].lazy;
        t[rt << 1 | 1].lazy |= t[rt].lazy;
        t[rt << 1].color |= t[rt].lazy;
        t[rt << 1 | 1].color |= t[rt].lazy;
        t[rt].lazy = 0;
    }
}

void update(int rt, int left, int right, int l, int r, int c)
{
    if (l <= left && r >= right)
    {
        t[rt].color |= (1 << c);
        t[rt].lazy |= (1 << c);
        return;
    }
    else
    {
        pushDown(rt);
        int mid = left + (right - left) / 2;
        if (l <= mid)
        {
            update(rt << 1, left, mid, l, r, c);
        }
        if (mid < r)
        {
            update(rt << 1 | 1, mid + 1, right, l, r, c);
        }
        
        t[rt].color = t[rt << 1].color | t[rt << 1 | 1].color;
    }
}

int query(int rt, int left, int right, int l, int r)
{
    if (l <= left && r >= right)    
    {
        return t[rt].color;
    }
    
    pushDown(rt);
    int result = 0;
    int mid = left + (right - left) / 2;
    if (l <= mid)
    {
        result |= query(rt << 1, left, mid, l, r);
    }
    if (r > mid)
    {
        result |= query(rt << 1 | 1, mid + 1, right, l, r);
    }
    
    return result;
}

int main()
{
    int m, n, a, b, c;
    char op;
    cin >> m >> n;
    build(1, 1, n);
    
    for (int i = 0; i < m; i++)
    {
        cin >> op;
        if (op == 'P')
        {
            cin >> a >> b >> c;
            update(1, 1, n, a, b, c);
        }
        else
        {
            cin >> a >> b;
            int color = query(1, 1, n, a, b);
            int result = 0;
            
            while (color)
            {
                result++;
                color &= (color - 1);
            }
            cout << result << endl;
        }
    }
    
    return 0;
}