牛客竞赛题目讲解_Different Integers(树状数组)

//  https://ac.nowcoder.com/acm/contest/20322/J  

#include <algorithm>

#include <iostream>

#include <cstring>

 #include <vector>

 #define endl '\n'

 

using namespace std;

const int maxn = 1e5 + 9; 

int n, m;

int first[maxn], lst[maxn], a[maxn], ans[maxn];

int cnt;

int c[maxn];

struct node{

    int l, r, id;

    bool operator<(const node &B){

        return r < B.r;

    }

}d[maxn];

 // 树状数组更新

/*

for(  i=1;i<=16;i++)

        printf("i =%2d,i&(-i) =%2d\n",i,i&(-i));

i&(-i) 给出 i 最低位的权重

*/

void update(int i, int k){

    while(i <= n) c[i] += k, i += i & (-i);    // 父节点

}

int qry(int i){

    int ans = 0;

    // 子节点, 如果i=3, 下一个节点为i=2

    while(i) ans += c[i], i -= i & (-i);    

    return ans; 

}

 

void work()

{

     cnt = 0;

    memset(first,0 ,sizeof first);

     memset(lst,0 ,sizeof lst);

    memset(c,0 ,sizeof c);

    

    for(int i = 1; i <= n; ++i){

        cin >> a[i];

        if(!first[a[i]]) first[a[i]] = i, ++cnt;

        lst[a[i]] = i;  

    }

    for(int i = 1; i <= m; ++i){

        cin >> d[i].l >> d[i].r;

        d[i].id = i;

    }

    sort(d + 1, d + 1 + m);

    int j = 1;

    for(int i = 1; i <= n; ++i){

        while(i == d[j].r && j <= m){// 因为数据包含 [r,n]，所以先求答案再更新 

            ans[d[j].id] = cnt + qry(d[j].l);

            ++j;    // j不能减少，所以按照d[j].r排序

        }

        if(lst[a[i]] == i){

            update(first[a[i]], 1);

            --cnt;

        }

    }

    for(int i = 1; i <= m; ++i) //cout << ans[i] << endl;

       printf("%d\n" ,ans[i] );

} 

int main()

{   

    while(cin >> n >> m)

    work();

    return 0;

}