POJ-2777-CountColor(线段树，位运算）-蒲公英云

POJ-2777-CountColor(线段树，位运算）

た入场券 2021-12-24 05:07 334阅读 0赞

链接：https://vjudge.net/problem/POJ-2777\#author=0

题意：

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:

“C A B C” Color the board from segment A to segment B with color C.
“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.

思路：

线段树，还是普通的线段树，染色的查询和更新使用位运算，因为颜色区间在（1-30）之内。

所以可以使用(1<<1-1<<30)来表示这中二进制1的个数来表示颜色的数量。

不过我之前的写的普通的线段树我也不知道为啥会WA。

代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <memory.h>
#include <algorithm>
#include <string>
#include <stack>
#include <vector>
#include <queue>
using namespace std;
typedef long long LL;
const int MAXN = 1e5+10;
int Seg[MAXN*4];
int lazy[MAXN*4];
int Vis[100];
int n, t, o;
int res;
void PushDown(int root)
{
    if (lazy[root] != 0)
    {
        Seg[root<<1] = (1<<lazy[root]);
        Seg[root<<1|1] = (1<<lazy[root]);
        lazy[root<<1] = lazy[root];
        lazy[root<<1|1] = lazy[root];
        lazy[root] = 0;
    }
}
void PushUp(int root)
{
    Seg[root] = Seg[root<<1]|Seg[root<<1|1];
}
void Build(int root, int l, int r)
{
    if (l == r)
    {
        Seg[root] = 2;
        return;
    }
    int mid = (l + r) / 2;
    Build(root << 1, l, mid);
    Build(root << 1 | 1, mid + 1, r);
    PushUp(root);
}
void Update(int root, int l, int r, int ql, int qr, int c)
{
    if (r < ql || qr < l)
        return;
    if (ql <= l && r <= qr)
    {
        Seg[root] = (1<<c);
        lazy[root] = c;
        return;
    }
    PushDown(root);
    int mid = (l+r)/2;
    Update(root<<1, l, mid, ql, qr, c);
    Update(root<<1|1, mid+1, r, ql, qr, c);
    PushUp(root);
}
int Query(int root, int l, int r, int ql, int qr)
{
    if (r < ql || qr < l)
        return 0;
    if (ql <= l && r <= qr)
    {
        return Seg[root];
    }
    int mid = (l+r)/2;
    PushDown(root);
    int col1 = 0, col2 = 0;
    col1 = Query(root<<1, l, mid, ql, qr);
    col2 = Query(root<<1|1, mid+1, r, ql, qr);
    return col1|col2;
}
int Get(int x)
{
    int res = 0;
    while (x)
    {
        if (x&1)
            res++;
        x >>= 1;
    }
    return res;
}
int main()
{
    char op[10];
    int a, b, c;
    while (~scanf("%d%d%d", &n, &t, &o))
    {
        Build(1, 1, n);
        while (o--)
        {
            scanf("%s", op);
            if (op[0] == 'C')
            {
                scanf("%d%d%d", &a, &b, &c);
                if (a > b)
                    swap(a, b);
                Update(1, 1, n, a, b, c);
            }
            else
            {
                scanf("%d%d", &a, &b);
                if (a > b)
                    swap(a, b);
                memset(Vis, 0, sizeof(Vis));
                int res = Query(1, 1, n, a, b);
                printf("%d\n", Get(res));
            }
        }
    }
    return 0;
}