GDUT - 专题学习5 F - Count Color

题目

Chosen Problem Solving and Program design as an optional course, you are required to solve all kinds of problems. Here, we get a new problem.

There is a very long board with length L centimeter, L is a positive integer, so we can evenly divide the board into L segments, and they are labeled by 1, 2, ... L from left to right, each is 1 centimeter long. Now we have to color the board - one segment with only one color. We can do following two operations on the board:

1. "C A B C" Color the board from segment A to segment B with color C.
2. "P A B" Output the number of different colors painted between segment A and segment B (including).

In our daily life, we have very few words to describe a color (red, green, blue, yellow…), so you may assume that the total number of different colors T is very small. To make it simple, we express the names of colors as color 1, color 2, ... color T. At the beginning, the board was painted in color 1. Now the rest of problem is left to your.

Input

First line of input contains L (1 <= L <= 100000), T (1 <= T <= 30) and O (1 <= O <= 100000). Here O denotes the number of operations. Following O lines, each contains "C A B C" or "P A B" (here A, B, C are integers, and A may be larger than B) as an operation defined previously.

Output

Ouput results of the output operation in order, each line contains a number.

Sample

Inputcopy	Outputcopy
2 2 4 C 1 1 2 P 1 2 C 2 2 2 P 1 2	2 1

题目大意

有一块很长的木板，长度为 L 厘米，L 是一个正整数，所以我们可以把板子平均分成 L 段，从左到右分别用 1、2、...L 标记，每段为 1 厘米长。现在给棋盘上色——一个段只有一种颜色。我们可以在板子上做以下两个操作：
1. "CABC" 用颜色 C 给从 A 段到 B 段的板着色。
2. "PAB" 输出 A 段和 B 段之间绘制的不同颜色的数量。

思路

使用线段树中的懒标记，首次修改颜色时不会将懒标记完全下传，在第二次查询的时候才往下传递懒标记。

其次这里可以观察到color种类比较少，所以我们可以用二进制数来代替即第k总颜色对于二进制的第k位，线段树则是维护的值num储存的所包含二进制位1的数量，即为颜色种类。

#include<iostream>
#include<iomanip>
#include<algorithm>
#include<math.h>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<queue>
#include<stack>
using namespace std;
#define ll long long
const int N = 1e5 + 5;
struct node 
{
    int l, r, num, lazy;
} tr[N << 2];
int col[31], n, t, m, temp = 1;
void bt(int u, int l, int r)
{
    if (l == r)
    {
        tr[u] = { l,r,1,0 };
    }
    else 
    {
        int mid = l + r >> 1;
        tr[u] = { l,r,1,0 };
        bt(u << 1, l, mid);
        bt(u << 1 | 1, mid + 1, r);
    }
}
void pushup(int u) 
{
    tr[u].num = (tr[u << 1].num | tr[u << 1 | 1].num);
}
void pushdown(int u) 
{
    if (tr[u].lazy == 0)
    {
        return;
    }
    tr[u << 1].num = tr[u].lazy;
    tr[u << 1 | 1].num = tr[u].lazy;
    tr[u << 1].lazy = tr[u << 1 | 1].lazy = tr[u].lazy;
    tr[u].lazy = 0;
}
void update(int u, int l, int r, int d) 
{
    if (l <= tr[u].l && tr[u].r <= r) 
    {
        tr[u].num = col[d];
        tr[u].lazy = col[d];
    }
    else 
    {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)
        {
            update(u << 1, l, r, d);
        }
        if (r > mid)
        {
            update(u << 1 | 1, l, r, d);
        }
        pushup(u);
    }
}
int query(int u, int l, int r) 
{
    if (l <= tr[u].l && tr[u].r <= r) 
    {
        return tr[u].num;
    }
    else 
    {
        int res = 0;
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid)
        {
            res |= query(u << 1, l, r);
        }
        if (r > mid)
        {
            res |= query(u << 1 | 1, l, r);
        }
        return res;
    }
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin >> n >> t >> m;
    for (int i = 1; i <= 30; i++) 
    {
        col[i] = temp;
        temp *= 2;
    }
    bt(1, 1, n);
    while (m--) 
    {
        char s[2];
        int l, r;
        cin >> s >> l >> r;
        if (l > r)swap(l, r);
        if (s[0] == 'C')
        {
            int d;
            cin >> d;
            update(1, l, r, d);
        }
        else
        {
            int u = query(1, l, r);
            int res = 0;
            while (u) 
            {
                if (u & 1)res++;
                u >>= 1;
            }
            cout << res << endl;
        }
    }
    return 0;
}