Count Color 【POJ - 2777】【线段树】

题目链接

  这道题一开始觉得处理颜色很繁琐，但是后来发现了个东西——T<=30，对于这个数据，似乎可以开成比特位（二进制）然后进行处理，会发现，这就是区间更新的线段树了。

  有几个坑，我跳进去过了，一个是初始化要为1（颜色1），其次A和B的大小是不固定，只说在[A, B]围成区间内，还有个WA就是因为我处理Query时候，之间返回的是颜色个数，这样显然不对，应当返回的就是比特位，然后退出循环再进行个数处理。

贴几组测试数据：

10 4 5
C 2 1 3
C 9 10 2
C 5 5 4
P 1 5
P 2 2

12 5 10
C 3 2 4
C 5 4 2
P 6 5
C 1 2 2
C 2 3 2
C 4 4 1
P 2 3
P 7 7
C 8 12 5
P 1 12

6 7 4
C 1 6 2
P 1 5
C 4 2 7
P 6 1

答案为：
3
1

2
1
1
3

1
2

完整代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
using namespace std;
typedef long long ll;
const int maxN=1e5+5;
int L, T, Q;
ll tree[maxN<<2], lazy[maxN<<2];
void buildTree(int rt, int l, int r)
{
    lazy[rt]=0;
    if(l==r)
    {
        tree[rt]=1;
        return;
    }
    int mid=(l+r)>>1;
    buildTree(rt<<1, l, mid);
    buildTree(rt<<1|1, mid+1, r);
    tree[rt]=tree[rt<<1] | tree[rt<<1|1];
}
void pushdown(int rt)
{
    if(lazy[rt])
    {
        lazy[rt<<1]=lazy[rt];
        tree[rt<<1]=lazy[rt];
        lazy[rt<<1|1]=lazy[rt];
        tree[rt<<1|1]=lazy[rt];
        lazy[rt]=0;
    }
}
void update(int rt, int l, int r, int ql, int qr, int val)
{
    if(ql<=l && qr>=r)
    {
        tree[rt]=( 1<<(val-1) );
        lazy[rt]=( 1<<(val-1) );
        return;
    }
    pushdown(rt);
    int mid=(l+r)>>1;
    if(ql>mid) update(rt<<1|1, mid+1, r, ql, qr, val);
    else if(qr<=mid) update(rt<<1, l, mid, ql, qr, val);
    else
    {
        update(rt<<1, l, mid, ql, mid, val);
        update(rt<<1|1, mid+1, r, mid+1, qr, val);
    }
    tree[rt]=tree[rt<<1] | tree[rt<<1|1];
}
int cnt(ll x)
{
    int ans=0;
    while(x)
    {
        if(x&1) ans++;
        x>>=1;
    }
    return ans;
}
ll Query(int rt, int l, int r, int ql, int qr)
{
    if( (ql<=l && qr>=r) || lazy[rt] )
    {
        return tree[rt];
    }
    ll ans=0;
    int mid=(l+r)>>1;
    if(ql>mid) ans=Query(rt<<1|1, mid+1, r, ql, qr);
    else if(qr<=mid) ans=Query(rt<<1, l, mid, ql, qr);
    else
    {
        ans=Query(rt<<1, l, mid, ql, mid);
        ans|=Query(rt<<1|1, mid+1, r, mid+1, qr);
    }
    return ans;
}
int main()
{
    while(scanf("%d%d%d", &L, &T, &Q)!=EOF)
    {
        buildTree(1, 1, L);
        char e1[3]; int e2, e3, e4;
        while(Q--)
        {
            scanf("%s", e1);
            if(e1[0]=='C')
            {
                scanf("%d%d%d", &e2, &e3, &e4);
                if(e2>e3) swap(e2, e3);
                update(1, 1, L, e2, e3, e4);
            }
            else
            {
                scanf("%d%d", &e2, &e3);
                if(e2>e3) swap(e2, e3);
                printf("%d\n", cnt(Query(1, 1, L, e2, e3)));
            }
        }
    }
    return 0;
}