Hossam and Range Minimum Query

题意翻译

+ 给你一个长度为 $n$ 的非负整数序列 $a$。 + 有 $q$ 次询问，每次询问 $[l,r]$ 中满足出现次数为**奇数**的数当中，**最小**的那个是哪个数，不存在则输出 $0$。 + 强制在线，你输入的 $l',r'$ 需要异或上上一次的答案 $\operatorname{lastans}$ 才是真正的 $l,r$，若此时为第一次询问或上一次询问不存在出现次数为奇数的数，则 $\operatorname{lastans}=0$。 + $1\leq n,q\leq 2\times10^5,0\leq a_i\leq 10^9,1\leq l',r'\leq2\times 10^9$。 Translated by [World_Creater](https://www.luogu.com.cn/user/122836)

题目描述

Hossam gives you a sequence of integers $ a_1, \, a_2, \, \dots, \, a_n $ of length $ n $ . Moreover, he will give you $ q $ queries of type $ (l, \, r) $ . For each query, consider the elements $ a_l, \, a_{l + 1}, \, \dots, \, a_r $ . Hossam wants to know the smallest number in this sequence, such that it occurs in this sequence an odd number of times. You need to compute the answer for each query before process the next query.

输入输出格式

输入格式

The first line of the input contains one integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ), the length of the sequence. The second line contains $ n $ integers $ a_1, \, a_2, \, \dots, \, a_n $ ( $ 1 \le a_i \le 10^9 $ ). The third line contains one integer $ q $ ( $ 1 \le q \le 2 \cdot 10^5 $ ), the number of queries. Each of the next $ q $ lines contains two integers $ a $ and $ b $ ( $ 0 \le a, \, b \le 2 \cdot 10^9 $ ), the numbers used to encode the queries. Let $ \mathrm{ans}_i $ be the answer on the $ i $ -th query, and $ \mathrm{ans}_0 $ be zero. Then $ $l_i = a_i \oplus \mathrm{ans}_{i - 1}, $ $ $ $ r_i = b_i \oplus \mathrm{ans}_{i - 1}, $ $ where $ l\_i, \\, r\_i $ are parameters of the $ i $ -th query and $ \\oplus $ means the <a href="https://en.wikipedia.org/wiki/Bitwise_operation#XOR">bitwise exclusive or</a> operation. It is guaranteed that $ 1 \\le l \\le r \\le n$.

输出格式

For each query, print the smallest number that occurs an odd number of times on the given segment of the sequence. If there is no such number, print $ 0 $ .

输入输出样例

输入样例 #1

5
1 2 1 2 2
6
1 2
0 2
0 6
0 5
2 2
3 7

输出样例 #1

1
2
1
0
2
2

输入样例 #2

10
51 43 69 48 23 52 48 76 19 55
10
1 1
57 57
54 62
20 27
56 56
79 69
16 21
18 30
25 25
62 61

输出样例 #2

51
55
19
48
76
19
23
19
55
19

说明

In the example, $ $l_1 = 1, \, r_1 = 2, $ $ $ $ l_2 = 1, \, r_2 = 3, $ $ $ $ l_3 = 2, \, r_3 = 4, $ $ $ $ l_4 = 1, \, r_4 = 4, $ $ $ $ l_5 = 2, \, r_5 = 2, $ $ $ $ l_6 = 1, \, r_6 = 5. $ $

**题目大意：**
Hossam给你一个长度为n的非负整数序列a。有q次询问，每次询问\[l,r]区间内出现次数为奇数的数中，最小的那个是哪个数，如果不存在则输出0。每次输入的l',r'需要与上一次的答案lastans进行异或操作才是真正的l,r，如果是第一次询问或上一次询问不存在出现次数为奇数的数，则lastans=0。

**输入格式：**
第一行包含一个整数n（1≤n≤2×10^5），表示序列的长度。

第二行包含n个整数a_1, a_2, …, a_n（0≤a_i≤10^9），表示序列的元素。

第三行包含一个整数q（1≤q≤2×10^5），表示询问的数量。

接下来q行，每行包含两个整数a和b（0≤a, b≤2×10^9），用于编码查询。

**输出格式：**
对于每个询问，输出序列给定区间内出现次数为奇数的最小的数。

如果不存在这样的数，则输出0。

**输入输出样例：**
**输入样例1：**
```
5
1 2 1 2 2
6
1 2
0 2
0 6
0 5
2 2
3 7
```
**输出样例1：**
```
1
2
1
0
2
2
```
**输入样例2：**
```
10
51 43 69 48 23 52 48 76 19 55
10
1 1
57 57
54 62
20 27
56 56
79 69
16 21
18 30
25 25
62 61
```
**输出样例2：**
```
51
55
19
48
76
19
23
19
55
19
```**题目大意：** Hossam给你一个长度为n的非负整数序列a。有q次询问，每次询问\[l,r]区间内出现次数为奇数的数中，最小的那个是哪个数，如果不存在则输出0。每次输入的l',r'需要与上一次的答案lastans进行异或操作才是真正的l,r，如果是第一次询问或上一次询问不存在出现次数为奇数的数，则lastans=0。 **输入格式：** 第一行包含一个整数n（1≤n≤2×10^5），表示序列的长度。 第二行包含n个整数a_1, a_2, …, a_n（0≤a_i≤10^9），表示序列的元素。 第三行包含一个整数q（1≤q≤2×10^5），表示询问的数量。 接下来q行，每行包含两个整数a和b（0≤a, b≤2×10^9），用于编码查询。 **输出格式：** 对于每个询问，输出序列给定区间内出现次数为奇数的最小的数。 如果不存在这样的数，则输出0。 **输入输出样例：** **输入样例1：** ``` 5 1 2 1 2 2 6 1 2 0 2 0 6 0 5 2 2 3 7 ``` **输出样例1：** ``` 1 2 1 0 2 2 ``` **输入样例2：** ``` 10 51 43 69 48 23 52 48 76 19 55 10 1 1 57 57 54 62 20 27 56 56 79 69 16 21 18 30 25 25 62 61 ``` **输出样例2：** ``` 51 55 19 48 76 19 23 19 55 19 ```