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;
}