Description

给定一个长度为n的数组a，有m次询问，每次询问区间[l,r][l, r]内是否存在只出现过一次的数字，如果有则任意输出一个即可

Hint

n,m,ai≤5∗105n, m, a_i\leq 5 * 10^5

Solution

我们考虑将询问离线，用扫描线和贪心的思想

设Pre[i]Pre[i]表示a[i]a[i]这个数上一次出现的位置，那么对于一个区间[l,r][l, r]，我们只需要看其中最小的Pre[i]Pre[i]是否比l小（线段树维护），即可判断是否存在，如果有则输出这个最小的Pre[i]Pre[i]

但是如果直接这么做的话，对于l≤i<j≤rl\leq i<j \leq r 且a[i]=a[j],Pre[i]<la[i] = a[j], Pre[i]<l的情况，我们会将a[i]a[i]统计进答案，而事实上这种情况是不符合题意的

对于这种情况，我们只需要在离线扫描线处理到ii时，将线段树中Pre[i]Pre[i]的值设为infinf

那么直接在线段树上查询最小值即可

Code

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
#define x first
#define y second
#define mp make_pair
#define pb push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;
template <typename T> inline int Chkmax (T &a, T b) {return a < b ? a = b, 1 : 0;}
template <typename T> inline int Chkmin (T &a, T b) {return a > b ? a = b, 1 : 0;}
template <typename T> T read()
{
	int fl = 1, sum = 0; char ch = getchar();
	while (ch < '0' || ch > '9') {if (ch == '-') fl = -1; ch = getchar();}
	while (ch >= '0' && ch <= '9') sum = sum * 10 + ch - '0', ch = getchar();
	return sum * fl;
}

const int Maxn = 5e5 + 100, inf = 0x3f3f3f3f;

int N, M, A[Maxn];
vector <pii> Q[Maxn];

namespace SEG
{
	pii Tree[Maxn << 2];

	inline void push_up (int root) { Tree[root] = min(Tree[root << 1], Tree[root << 1 | 1]); }

	inline void update (int root, int l, int r, int x, pii v)
	{
		if (l == r) { Tree[root] = v; return ; }
		int mid = (l + r) >> 1;
		if (x <= mid) update (root << 1, l, mid, x, v);
		else update (root << 1 | 1, mid + 1, r, x, v);
		push_up(root);
	}

	inline pii query (int root, int l, int r, int x, int y)
	{
		if (l > y || r < x) return {inf, inf};
		if (x <= l && r <= y) return Tree[root];
		int mid = (l + r) >> 1;
		pii ans = {inf, inf};
		if (x <= mid) ans = min(ans, query (root << 1, l, mid, x, y));
		if (y > mid) ans = min(ans, query (root << 1 | 1, mid + 1, r, x, y));
		return ans;
	}
}

inline void Input()
{
	N = read<int>();
	for (int i = 1; i <= N; ++i) A[i] = read<int>();
	M = read<int>();
	for (int i = 1; i <= M; ++i)
	{
		int x = read<int>(), y = read<int>();
		Q[y].pb({x, i});
	}
}

pii Pre[Maxn];
int id[Maxn], Ans[Maxn];

int main()
{
#ifdef hk_cnyali
	freopen("F.in", "r", stdin);
	freopen("F.out", "w", stdout);
#endif
	Input();

	for (int i = 1; i <= N; ++i)
	{
		Pre[i] = {id[A[i]], A[i]};
		id[A[i]] = i;
	}
	for (int i = 1; i <= N; ++i)
	{
		if (Pre[i].x) SEG :: update(1, 1, N, Pre[i].x, {inf, inf});
		SEG :: update(1, 1, N, i, Pre[i]);
		for (int j = 0; j < Q[i].size(); ++j)
		{
			pii x = Q[i][j], ans = SEG :: query(1, 1, N, x.x, i);
			if (ans.x < x.x) Ans[x.y] = ans.y;
		}
	}
	for (int i = 1; i <= M; ++i) printf("%d\n", Ans[i]);
	return 0;
}