首先将原数组扩展为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;
}
分类: 未分类

发表评论

电子邮件地址不会被公开。 必填项已用*标注

隐藏
变装