CF2153F Odd Queries on Odd Array

An array $ b $ of length $ m $ is cute if there do not exist four indices $ 1\le i < j < k < l \le m $ such that $ b_i\neq b_j $ , $ b_i = b_k $ and $ b_j = b_l $ . The beauty of an array $ b $ of length $ m $ is defined as the sum of all distinct values that appear an odd number of times in array $ b $ . Formally, let $ \operatorname{cnt}(b, x) $ denote the number of times the value $ x $ appears in array $ b $ . Then, the beauty is given by $$$ \sum\limits_{\substack{x\in \mathbb{Z}\\\operatorname{cnt}(b, x)\text{ is odd}}}x. $$$ You are given a cute array $ a $ of length $ n $ , and you need to answer $ q $ queries online. Each query consists of two integers $ l $ and $ r $ ( $ 1\le l\le r\le n $ ), and you must compute the beauty of the subarray $ a_{l\ldots r} $ $ ^{\text{∗}} $ . Note that the queries are encoded; each subsequent query can only be decoded after calculating the answer to the preceding query. $ ^{\text{∗}} $ The subarray $ a_{l \ldots r} $ refers to the contiguous segment of the array $ a $ that starts at index $ l $ and ends at index $ r $ , i.e., $ [a_l, a_{l+1}, \ldots, a_r] $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ q $ ( $ 1\le n, q\le 5\cdot 10^5 $ ) — the length of array $ a $ and the number of queries. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1\le a_i\le n $ ) — the elements of the cute array $ a $ . The $ i $ -th of the next $ q $ lines contains two integers $ x'_i $ and $ y'_i $ ( $ 1\le x'_i, y'_i\le n $ ) — the endpoints of the queried subarray in an encoded form. Let $ \text{ans}_i $ be the answer to the $ i $ -th query, with $ \text{ans}_0 = 0 $ . Then, we calculate $ x_i = ((x'_i - 1 + \text{ans}_{i - 1}) \bmod n) + 1 $ and $ y_i = ((y'_i - 1 + \text{ans}_{i - 1}) \bmod n) + 1 $ . The endpoints of the $ i $ -th queried subarray, $ l_i $ and $ r_i $ , are decoded as $ l_i = \min(x_i, y_i) $ and $ r_i = \max(x_i, y_i) $ . It is guaranteed that the given array $ a $ satisfies the conditions of a cute array. It is guaranteed that the sum of $ n $ and the sum of $ q $ over all test cases does not exceed $ 5\cdot 10^5 $ .

For each test case, output $ q $ integers representing the answers to each query.

In the first test case, the queries are as follows: - $$$ x_1 = ((7 - 1 + 0) \bmod 11) + 1 = 7, \quad y_1 = ((10 - 1 + 0) \bmod 11) + 1 = 10 $$$$$$ l_1 = \min(7, 10) = 7, \quad r_1 = \max(7, 10) = 10 $$$ Thus, the queried subarray is $ a_{7\ldots 10} = [3, 2, 2, 1] $ . Values $ 3 $ and $ 1 $ appear once (odd), and value $ 2 $ appears twice (even). Hence, the beauty is $ 3 + 1 = 4 $ . - $$$ x_2 = ((5 - 1 + 4) \bmod 11) + 1 = 9, \quad y_2 = ((11 - 1 + 4) \bmod 11) + 1 = 4 $$$$$$ l_2 = \min(9, 4) = 4, \quad r_2 = \max(9, 4) = 9 $$$ Thus, the queried subarray is $ a_{4\ldots 9} = [2, 3, 3, 3, 2, 2] $ . Values $ 2 $ and $ 3 $ appear three times (odd). Hence, the beauty is $ 2 + 3 = 5 $ . - $$$ x_3 = ((8 - 1 + 5) \bmod 11) + 1 = 2, \quad y_3 = ((6 - 1 + 5) \bmod 11) + 1 = 11 $$$$$$ l_3 = \min(2, 11) = 2, \quad r_3 = \max(2, 11) = 11 $$$ Thus, the queried subarray is $ a_{2\ldots 11} = [1, 2, 2, 3, 3, 3, 2, 2, 1, 1] $ . Values $ 1 $ and $ 3 $ appear three times (odd), and value $ 2 $ appears four times (even). Hence, the beauty is $ 1 + 3 = 4 $ . - $$$ x_4 = ((2 - 1 + 4) \bmod 11) + 1 = 6, \quad y_4 = ((8 - 1 + 4) \bmod 11) + 1 = 1 $$$$$$ l_4 = \min(6, 1) = 1, \quad r_4 = \max(6, 1) = 6 $$$ Thus, the queried subarray is $ a_{1\ldots 6} = [1, 1, 2, 2, 3, 3] $ . Values $ 1 $ , $ 2 $ , and $ 3 $ each appear twice (even). Hence, the beauty is $ 0 $ . In the second test case, the queries are as follows: - $$$ x_1 = ((1 - 1 + 0) \bmod 6) + 1 = 1, \quad y_1 = ((6 - 1 + 0) \bmod 6) + 1 = 6 $$$$$$ l_1 = \min(1, 6) = 1, \quad r_1 = \max(1, 6) = 6 $$$ Thus, the queried subarray is $ a_{1\ldots 6} = [1, 3, 2, 3, 4, 3] $ . Values $ 1 $ , $ 2 $ , and $ 4 $ appear once (odd), and value $ 3 $ appears three times (odd). Hence, the beauty is $ 1 + 2 + 3 + 4 = 10 $ . - $$$ x_2 = ((1 - 1 + 10) \bmod 6) + 1 = 5, \quad y_2 = ((4 - 1 + 10) \bmod 6) + 1 = 2 $$$$$$ l_2 = \min(5, 2) = 2, \quad r_2 = \max(5, 2) = 5 $$$ Thus, the queried subarray is $ a_{2\ldots 5} = [3, 2, 3, 4] $ . Values $ 2 $ and $ 4 $ appear once (odd), and value $ 3 $ appears twice (even). Hence, the beauty is $ 2 + 4 = 6 $ . In the third test case, all elements of array $ a $ are equal to $ 3 $ . - For any subarray of odd length, the value $ 3 $ appears an odd number of times, so the beauty is $ 3 $ . - For any subarray of even length, the value $ 3 $ appears an even number of times, so the beauty is $ 0 $ .