牛客网暑期ACM多校训练营（第一场）J 题解

这题是这场的签到题，每次查询求a[1...l]和a[r...n]有多少种不同的数字

这题做法很多，有***树、莫队、离线树状数组。

***树和莫队都是很多人T了的，包括我们队在内，这里我就讲一下离线树状数组的做法。

首先将原数组扩展为2倍长的，即 a[i+n] = a[i]

对于查询a[1...l]和a[r..n]有多少种不同的数字可以转换为查询 a[r...l+n]有多少种不同的数字

首先考虑维护一个前缀和，pre[i]表示a[1...i]有多少种不同的数字，那么对于a[l...r]的答案就为pre[r] - pre[l-1] + 在a[l...r]和a[1...l-1]同时出现的数字的种类

对于如何求在a[l...r]和a[1...l-1]同时出现的数字的种类，可以考虑使用树状数组维护，树状数组的第i个点表示a[i]是否已经在1...l出现过，对于每个查询只需要查树状数组中l~r的区间和即可

那么我们只要对区间查询进行排序，对于左端每次右移的时候把对应的数的下一个位置加入到数状数组中即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+10;

int n, q;
int a[N];
int pre[N];     //pre[i]表示数组前i个数有多少种不同的数
bool vis[N];
int last[N];    //用来计算nxt数组用的辅助数组，记录每个数上一次出现的位置
int nxt[N];     //用来维护数组中每个位置的数下一次出现的位置
int ans[N];

struct Q{
    int l, r, id;
    bool operator < (const Q &b) const {    //将查询按照左端点排序
        return this->l < b.l;
    }
}query[N];

int bit[N];
int lowbit(int x){
    return x & -x;
}
void update(int x, int y){
    for(int i = x; i < N; i += lowbit(i)){
        bit[i] += y;
    }
}

int Query(int x){
    int ans = 0;
    for(int i = x; i > 0; i -= lowbit(i)){
        ans += bit[i];
    }
    return ans;
}

int Query(int l, int r){
    return Query(r) - Query(l-1);
}


int main(){
#ifdef local
    freopen("in","r",stdin);
#endif
    while(scanf("%d%d", &n, &q)!=EOF){
        memset(bit, 0, sizeof(bit));
        memset(vis, 0, sizeof(vis));
        memset(nxt, -1, sizeof(nxt));
            memset(last, -1, sizeof(last));
        for(int i = 1; i <= n; ++i){
            scanf("%d", &a[i]);
            a[i+n] = a[i];
        }
        n *= 2;
        pre[0]=0;
        for(int i = 1; i <= n; ++i){
            if(!vis[a[i]]){
                vis[a[i]] = true;
                pre[i] = pre[i-1] + 1;
            }
            else{
                pre[i] = pre[i-1];
            }
            if(~last[a[i]]){
                nxt[last[a[i]]] = i;
            }
            last[a[i]] = i;
        }
        for(int i = 0; i < q; ++i){
            scanf("%d%d", &query[i].l, &query[i].r);
            query[i].l += n/2;
            swap(query[i].l, query[i].r);
            query[i].id = i;
        }
        sort(query, query+q);
        int nowl = 1;
        for(int i = 0; i < q; ++i){
            while(nowl < query[i].l){
                if(~nxt[nowl]){
                    update(nxt[nowl], 1);
                }
                ++nowl;
            }
            ans[query[i].id] = pre[query[i].r] - pre[query[i].l-1] + Query(query[i].l, query[i].r);
        }
        for(int i = 0; i < q; ++i){
            printf("%d\n",ans[i]);
        }
    }
    return 0;
}