cdoj 1259 线段树+bitset

链接：戳这里

昊昊喜欢运动

他NN天内会参加M种运动(每种运动用一个[1,m]的整数表示)

现在有Q个操作，操作描述如下

昊昊把第l天到第r天的运动全部换成了x，x∈[1,m])

问昊昊第l天到第r天参加了多少种不同的运动

Input

输入两个数N, M (1≤N≤105, 1≤M≤100);

输入N个数ai(ai∈[1,m]表示在第i天昊昊做了第ai类型的运动;

输入一个数Q(1≤Q≤105);

输入Q行 每行描述以下两种操作

形如M l r x，表示昊昊把第ll天到第rr天的运动全部换成了x x∈[1,m])

形如Q l r，表示昊昊想知道他第l天到第r天参加了多少种不同的运动

Output

对于所有的Q操作，每一行输出一个数 表示昊昊在第ll天到第rr天一共做了多少种活动

Sample input and output

Sample Input

5 3

1 2 3 2 3

4

Q 1 4

Q 2 4

M 5 5 2

Q 1 5

Sample Output

3

2

3

思路：

线段树处理区间种类出现的个数

bitset：处理二进制位的有序集。快速统计两个集合中数字出现的次数

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include <ctime>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<iomanip>
#include<cmath>
#include<bitset>
#define mst(ss,b) memset((ss),(b),sizeof(ss))
///#pragma comment(linker, "/STACK:102400000,102400000")
typedef long long ll;
#define INF (1ll<<60)-1
#define Max 1e9
using namespace std;
int n,m,q;
int a[100100];
bitset<110> tr[400100];
int lazy[400100];
void build(int root,int l,int r){
    if(l==r){
        tr[root].reset();
        tr[root][a[l]]=1;
        lazy[root]=0;
        return ;
    }
    int mid=(l+r)/2;
    build(root*2,l,mid);
    build(root*2+1,mid+1,r);
    tr[root]=tr[root*2]|tr[root*2+1];
}
void pushdown(int root){
    if(lazy[root]){
        tr[root*2].reset();
        tr[root*2+1].reset();
        tr[root*2][lazy[root]]=1;
        tr[root*2+1][lazy[root]]=1;
        lazy[root*2]=lazy[root*2+1]=lazy[root];
        lazy[root]=0;
    }
}
void update(int root,int l,int r,int x,int y,int v){
    if(x<=l && y>=r){
        tr[root].reset();
        tr[root][v]=1;
        lazy[root]=v;
        return ;
    }
    pushdown(root);
    int mid=(l+r)/2;
    if(y<=mid) update(root*2,l,mid,x,y,v);
    else if(x>mid) update(root*2+1,mid+1,r,x,y,v);
    else {
        update(root*2,l,mid,x,mid,v);
        update(root*2+1,mid+1,r,mid+1,y,v);
    }
    tr[root]=tr[root*2]|tr[root*2+1];
}
bitset<110> query(int root,int l,int r,int x,int y){
    if(x<=l && y>=r) {
        return tr[root];
    }
    pushdown(root);
    int mid=(l+r)/2;
    if(y<=mid) return query(root*2,l,mid,x,y);
    else if(x>mid) return query(root*2+1,mid+1,r,x,y);
    else {
        return query(root*2,l,mid,x,mid)|query(root*2+1,mid+1,r,mid+1,y);
    }
}
char c;
int l,r,v;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    build(1,1,n);
    scanf("%d",&q);
    while(q--){
        getchar();
        scanf("%c",&c);
        if(c=='Q'){
            scanf("%d%d",&l,&r);
            printf("%d\n",query(1,1,n,l,r).count());
        } else {
            scanf("%d%d%d",&l,&r,&v);
            update(1,1,n,l,r,v);
        }
    }
    return 0;
}