One Occurrence(过程看注释)

题面翻译

题目大意：

给定一个长度为$n$序列，$m$个询问，每次询问给定一个区间$[l,r]$，如果这个区间里存在只出现一次的数，输出这个数（如果有多个就输出任意一个），没有就输出0，$n,m<=5\ast 10^5$

输入格式：

第一行一个整数$n$

接下来1行$n$个小于$5\ast 10^5$的正整数，即序列

下面一行一个整数$m$

在下面$m$行，每行两个整数$l,r$

输入格式：

共$m$行，如题目

感谢@守望 提供翻译

题目描述

You are given an array $a$ consisting of $n$ integers, and $q$ queries to it. $i$ -th query is denoted by two integers $l_i$ and $r_i$ .

For each query, you have to find any integer that occurs exactly once in the subarray of $a$ from index $l_i$ to index $r_i$ (a subarray is a contiguous subsegment of an array).

For example, if $a=[1,1,2,3,2,4]$ , then for query $(l_i=2,r_i=6)$ the subarray we are interested in is $[1,2,3,2,4]$ , and possible answers are $1$ , $3$ and $4$ ; for query $(l_i=1,r_i=2)$ the subarray we are interested in is $[1,1]$ , and there is no such element that occurs exactly once.

Can you answer all of the queries?

输入格式

The first line contains one integer $n$ ( $1\le n\le 5\cdot 10^5$ ).

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ( $1\le a_i\le 5\cdot 10^5$ ).

The third line contains one integer $q$ ( $1\le q\le 5\cdot 10^5$ ).

Then $q$ lines follow, $i$ -th line containing two integers $l_i$ and $r_i$ representing $i$ -th query ( $1\le l_i\le r_i\le n$ ).

输出格式

Answer the queries as follows:

If there is no integer such that it occurs in the subarray from index $l_i$ to index $r_i$ exactly once, print $0$ .

Otherwise print any such integer.

样例 #1

样例输入 #1

6
1 1 2 3 2 4
2
2 6
1 2
1
2
3
4
5

样例输出 #1

4
0
1
2

#include
using namespace std;
const int N=1e6+10;
typedef long long ll;
struct modui{
    int l,r,id;
}s[N];
ll a[N],c[N],ans[N],stackk[N],id[N],top;
int L=1,R=0,pos[N],n,m,t;
void add(int x){
    c[x]++;
    //如果该数出现1次进栈放栈顶，并记录该数在栈位置
    if(c[x]==1) stackk[++top]=x,id[x]=top;
    //如果该数出现2次为不符合时
    //通过桶来寻找这个数在栈中的下标，然后把栈顶放入这个位置，再弹出栈顶
	if(c[x]==2) stackk[id[x]]=stackk[top],id[stackk[top]]=id[x],stackk[top]=id[x]=0,top--;
    return;
}
void del(int x){
    c[x]--;
    //如果该数出现1次进栈放栈顶，并记录该数在栈位置
    if(c[x]==1) stackk[++top]=x,id[x]=top;
    //如果该数出现0次为不符合时
    //通过桶来寻找这个数在栈中的下标，然后把栈顶放入这个位置，再弹出栈顶
	if(c[x]==0) stackk[id[x]]=stackk[top],id[stackk[top]]=id[x],stackk[top]=id[x]=0,top--;
    return ;
}
bool cmp(modui x,modui y){//按左端点分块，然后在同一个块当中区间右端点要递增
	if (pos[x.l]!=pos[y.l]) return x.l<y.l;
    if(pos[x.l]&1) return x.r<y.r;//奇偶性优化
	return x.r>y.r;//都是为了加速
}
void query(int l,int r){//移动指针的时候，对应地去删除或添加对答案的贡献
	while (L<l) del(a[L++]);//左指针往右移删除
	while (L>l) add(a[--L]);//左指针往左移加入
	while (R<r) add(a[++R]);//右指针往右移加入
	while (R>r) del(a[R--]);//右指针往左移删除
	return;
}
int main(){
    cin>>n;
    int dis=sqrt(n);//块大小 
    //pos标记每个数所属的分块
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),pos[i]=i/dis;
    cin>>m;
    for(int i=1;i<=m;i++){
		scanf("%d %d",&s[i].l,&s[i].r);
		s[i].id=i;//排序将会打乱原有的询问顺序,借此离线
	}
    sort(s+1,s+m+1,cmp);//排序的时候按照左端点所在的块为第一关键字，右端点为第二关键字排序
    for(int i=1;i<=m;i++){
		query(s[i].l,s[i].r);
		ans[s[i].id]=stackk[top];//记录答案
	}
	for(int i=1;i<=m;i++) printf("%lld\n",ans[i]);
	return 0;
}
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