[POJ 2777]Count Color[セグメントツリー区間更新クエリー]

タイトルリンク:[POJ 2777]Count Color[セグメントツリー区間更新クエリー]題意分析:長さLの長板を与え、L個のユニットに分割し、各ユニットの初期時の色は1である.まず、変更区間l、rが色cとクエリー区間l、rの中で何種類の異なる色があるかを含むO個の操作を与えます.色数は30個を超えない.问题の考え方:问题は検索する必要があるのは区间の中で何种类の异なる色があって、色の数はまた30个を超えないで、私达はバイナリで1つの区间の中で持つ色を表すことができて、更新する时2つのサブ区间のあるいはに等しくて、それから何个の1があるかを検索します.やはりこの関数XDを丁寧にお勧めしなければなりません

__builtin_popcount() //      1   

个人感受:debugはまる2时间、莫名A、それからデータを探して、原因を探して、最后にバイナリの表示の上で问题が発生したことを発见しました==具体的なコードは以下の通りです:

#include<iostream>
#include<cstdio>
#define root 1, n, 1
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
#define pr(x) cout << #x << '=' << (x) << '
';
using namespace std;

const int MAXN = 1e5 + 111;

int color[MAXN << 2], add[MAXN << 2];

void push_up(int rt)
{
    color[rt] = color[rt << 1] | color[rt << 1 | 1];
}

void push_down(int rt, int l, int r)
{
    if (add[rt] != -1)
    {
        add[rt << 1] = add[rt << 1 | 1] = add[rt];
        color[rt << 1] = color[rt << 1 | 1] = 1 << add[rt];
        add[rt] = -1;
    }
}

void build(int l, int r, int rt)
{
    add[rt] = -1;
    if (l == r)
    {
        color[rt] = 1;
        return;
    }
    int m = l + r >> 1;
    build(lson);
    build(rson);
    push_up(rt);
}

int query(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        return color[rt];
    }
    push_down(rt, l, r);
    int ret = 0;
    int m = l + r >> 1;
    if (L <= m) ret |= query(L, R, lson);
    if (m < R) ret |= query(L, R, rson);
    return ret;
}

void update(int L, int R, int val, int l, int r, int rt)
{
    if (L <= l && r <= R)
    {
        add[rt] = val;
        color[rt] = 1 << val;
        return;
    }
    push_down(rt, l, r);
    int m = l + r >> 1;
    if (L <= m) update(L, R, val, lson);
    if (m < R) update(L, R, val, rson);
    push_up(rt);
}

int main()
{
    int n, t, o; scanf("%d%d%d", &n, &t, &o);
    build(root);
    char op[2];
    int l, r, col;
    while (o --)
    {
        scanf("%s %d %d", op, &l, &r);
        if (l > r) swap(l, r);
        if (op[0] == 'C')
        {
            scanf("%d", &col);
            update(l, r, col - 1, root); // 1 << 0        
        }
        else
        {
            printf("%d
", __builtin_popcount(query(l, r, root)));
        }
    }
    return 0;
}