[nowcoder1]J. Different Integers

题意

给出一段序列$a_1,a_2,…,a_n$，和$l,r$，求区间$[1,l],[r,n]$中不同数字的个数。

题解

树状数组+倍增序列

将查询的$l,r$转化为查询序列$[r,l+n]$中不同中数字的个数。

使用$pre[]$数组维护一个前缀不同种类数字的个数。针对查询就是$pre[r]-pre[l-1]$再加上同时出现在$[1,l-1]$和$[l,r]$上的元素，因为在计算$pre[r]$的时候对于和$[1,l-1]$序列中相同的元素是剔除的，但是减掉之后是需要再加上去的。

对于查询$a[l,…,r]$和$a[1,…,l-1]$内同时出现数字的种类，可以使用树状数组来进行维护。$bit[i]$表示$a[i]$已经在$1,…,l$出现过了。

先对区间查询进行离线排序操作，对于左端每次右移把对应的数的下一个位置加入到树状数组中即可。(嘤嘤嘤？)

tips:处理每个位置数字下一次出现位置的方式很巧妙哦！

//last 记录上一个出现该数字的位置
//nxt 记录下一个出现该数字的位置
rep(i,1,n+1){
    if(!vis[a[i]]){
        vis[a[i]] = 1;
        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;
}

AC代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 2e5 + 10;
int a[maxn],last[maxn],nxt[maxn],vis[maxn],pre[maxn],bit[maxn];
int n,q;
struct node{
    int l,r,id;
    bool operator<(const node& x){
        return l < x.l;
    }
}ask[maxn];
int lowbit(int x){return x&-x;}
void update(int x,int val){
    for(int i=x;i<=n*2;i+=lowbit(i)){
        bit[i] += val;
    }
}
int query(int x){
    int s = 0;
    for(int i=x;i;i-=lowbit(i)){
        s += bit[i];
    }
    return s;
}
int query(int l,int r){
    return query(r) - query(l-1);
}
void init(){
    memset(vis,0,sizeof(vis));
    memset(last,-1,sizeof(last));
    memset(nxt,-1,sizeof(nxt));
    memset(bit,0,sizeof(bit));
}
int main(){
#ifdef LOCAL
    freopen("j.in","r",stdin);
#endif
    while(~scanf("%d%d",&n,&q)){
        init();
        rep(i,1,n+1) scanf("%d",&a[i]),a[i+n] = a[i];
        rep(i,1,n+n+1){
            if(!vis[a[i]]){
                pre[i] = pre[i-1] + 1;
                vis[a[i]] = 1;
            }else{
                pre[i] = pre[i-1];
            }
            if(~last[a[i]]) nxt[last[a[i]]] = i;
            last[a[i]] = i;
        }
        rep(i,0,q){
            int l,r;scanf("%d%d",&l,&r);
            int temp = l;l = r;r = temp + n;
            ask[i].l = l;ask[i].r = r;ask[i].id = i;
        }
        sort(ask,ask+q);
        int nowl = 1;
        int ans[maxn];
        rep(i,0,q){
            while(nowl < ask[i].l){
                if(~nxt[nowl])update(nxt[nowl],1);
                nowl++;
            }
            ans[ask[i].id] = pre[ask[i].r] - pre[ask[i].l-1] +query(ask[i].l,ask[i].r);
        }
        rep(i,0,q) printf("%d\n",ans[i]);
    }
    return 0;
}

Reference:https://www.nowcoder.com/discuss/87249?type=101&order=0&pos=12&page=1