[nowcoder1] J.Different Integers

[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:处理每个位置数字下一次出现位置的方式很巧妙哦!

1
2
3
4
5
6
7
8
9
10
11
12
//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代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#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