CDOJ(Lutece)_1256_昊昊爱运动_线段树+bitset

本文代码省略库和namespace声明，其中read()函数是读入数值的函数。

昊昊喜欢运动
他 N 天内会参加 M 种运动(每种运动用一个 [1,m] 的整数表示)
舍友有 Q 个问题
问昊昊第 l 天到第 r 天参加了多少种不同的运动
Standard Input
输入两个数 N, M (1 ≤ N ≤ 2000, 1 ≤ M ≤ 100);
输入 N 个数 a_i ，表示在第 i 天昊昊做了第 a_i 类型的运动;
输入一个数 Q (1 ≤ Q ≤ 10⁶);
输入 Q 行 每行两个数 l, r (1 ≤ l ≤ r ≤ n);
Standard Output
一共 Q ，每一行输出一个数表示昊昊在第 l 天到第 r 天一共做了多少种活动
Limit
1000ms / 64Mib

看到区间查询的第一反应是线段树，于是就要考虑如何储存数据。
考虑到最多有 100 种运动类型，即使我们用类似“状态压缩”的办法来储存，也需要保存到 2¹⁰⁰-1 ，显然把这个值作为数组下标是非常不合适的，于是考虑到使用 bitset 进行储存，经过计算是可行的。
在线段树的 pushup 操作中使用或运算来“合并”区间内包含的所有运动，用 bitset.count() 来统计 bitset 内 1 的个数，即运动的种类数，输出即可。
注意，为了进行时空复杂度优化，不需要在每一次 query 中都新建一个 bitset 进行合并子区间和返回，而是在总的 query 前建一个用于统计的 bitset ，给 query 传递地址进行或运算即可。

据说本题有很多种解法，包括DP甚至暴力（评测机性能太好了），有时间还会研究！

struct node 
{
    bitset<101>spo; // spo，即sport的缩写，表示该节点包含的运动信息，第 i 位为 1 表示有第 i 种运动。
}rt[8100];

int n,m,a[2001],q,LL,RR,tmp;

inline void rush(int id)
{
        rt[id].spo=rt[id<<1].spo|rt[(id<<1)+1].spo;
}

void build(int id,int l,int r)
{
    if(l==r) { read(tmp); rt[id].spo[tmp]=1; return; }
    int mid=(l+r)>>1;
    build(id<<1,l,mid);
    build((id<<1)+1,mid+1,r);
    rush(id);
}

void query(int id,int l,int r,int L,int R,bitset<101> &t)
{
    if(L<=l&&r<=R)
    {
        t=t|rt[id].spo;
        return ;
    }
    int mid=(l+r)>>1;
    if(L<=mid) query(id<<1,l,mid,L,R,t);
    if(R>mid) query((id<<1)+1,mid+1,r,L,R,t);
}

int main()
{
    read(n); read(m);
    build(1,1,n);
    read(q);
    while(q--)
    {
        read(LL); read(RR);
        bitset<101>_t;
        query(1,1,n,LL,RR,_t);
        printf("%d\n",_t.count());
    }
    return 0;
}