小编lit*_*urs的帖子

给定数组 A 由 N (1 <= N <= 10^5) 个小于 10^6 的正整数组成。给定 Q (1 <= Q <= 10^5) 个查询，对于 (L, R) (1 <= L <= R <= N) 形式的每个查询，打印出：

min(A[L], max(A[L+1], min(A[L+2], ...A[R]))))

请注意，我们不取 (A[L+2], A[L+3], ..., A[R-1], a[R]) 的最小值。“Min”和“max”是交错的。

• 例如：A[10] = {3, 1, 4, 5, 5, 2, 7, 8, 1, 1} 和 1 个查询 (1, 8)：

min(A[1], max(A[2], min(A[3], max(A[4], min(A[5], max(A[6], min(A[7], A[8])))))))

= min(3, max(1, min(4, max(5, min(5, max(2, min(7, 8)))))))

= min(3, …

问题是：

最初，序列是空的。有 n 个查询和 4 种查询类型：

• add(x)：将x添加到序列中，如果序列中已有x，则仍添加x。
• 删除（x）：从序列中删除x 1次。
• Xor(x)：将序列中的所有N替换为N xor x。
• Sum(K)：求序列中k个最小元素的总和。
• 0 <= x、n、K <= 10^5

对于每个查询 sum(x)，输出序列中 x 个最小元素的总和。

输入：

7
Add(4)      // A[] = {4}
Remove(3)   // A[] = {4}
Add(2)      // A[] = {4, 2}
Sum(2)      // A[] = {4, 2} => Output: 6
Xor(2)      // A[] = {4^2, 2^2} = {6, 0}
Sum(1)      // A[] = {6, 0} => Output: 0
Sum(2)      // A[] = {6, 0} => Output: 6 …

Run Code Online (Sandbox Code Playgroud)