子序列 (sequence)
题目描述
给定一个长度为 \(N\) 的序列 \(A\)。对于一个子序列，若任意两个在子序列中相邻的元素 \(A_x,A_y (x<y)\),都满足 \(A_x < A_y\),且原序列的区间 \([x,y)\) 中不存在严格大于 \(A_x\) 的值，那么我们就说这个子序列是"贪心上升"的。
定义一个子序列的权值为子序列中所有元素的和，给定 \(Q\) 次询问，每次询问给定一个区间 \([L,R]\) ,请你求出这个区间中权值最大的贪心上升子序列的权值是多少。
强制在线
输出格式
一行，输出一个非负整数，表示所有答案的异或和。
样例 #1
样例输入 #1
8 4 0 114514 6 5 7 3 8 4 5 7样例输出 #1
21样例 #2
样例输入 #2
10 5 1 1919810 3 2 3 0 8 5 7 2 6 9样例输出 #2
6提示
样例解释：
对于样例 1 的每个询问，\(L,R\) 和这个询问的答案依次为：
1 1 6 5 8 16 2 4 12 3 6 15对于样例 2 的每个询问， \(L,R\) 和这个询问的答案依次为：
3 8 12 1 9 13 10 10 9 7 9 8 9 9 6数据范围：
Subtask Score \(N \le\) \(Q \le\) \(T=\) Time Limit \(0\) \(10\) \(300\) \(300\) \(0\) \(1s\) \(1\) \(20\) \(3000\) \(3000\) \(0\) \(1s\) \(2\) \(20\) \(3 \times 10^5\) \(3 \times 10^5\) \(0\) \(5s\) \(3\) \(20\) \(3 \times 10^5\) \(3 \times 10^5\) \(1\) \(5s\) \(4\) \(30\) \(5 \times 10^5\) \(10^7\) \(1\) \(5s\) subtask1(10pts): \(N,Q \le 300,t=0\).
subtask2(20pts): \(N,Q \le 3000,t=0\).
subtask3(20pts): \(N,Q \le 3 \times 10^5,t=0\).
subtask4(20pts): \(N,Q \le 3 \times 10^5\).
subtask5(30pts): \(N \le 5\times 10^5,Q \le 10^7\).
对于所有数据，保证满足 \(0 \le a_i,S \le 10^9，T \in [0,1]\).
- 出题人： T4 是一道很有意思的题。不过我感觉比 T3 要简单？(我不会不配说话)
- 说一下 \(n \leq 3 \times 10^5, T = 0\) 的部分分。从左到右扫描线，对于一个 \(a_i\) 用单调栈找到前面一个最近的 \(a_j > a_i\) ，则在区间 \([j + 1, i]\) 会产生 \(+a_i\) 的贡献，直接求和即可
- 然后 \(T=1\) 就是主席树
- 最后正解：考虑在区间中找到一个最大值，并把问题分治为最大值前和最大值后的问题。
- 在最大值前面的部分，可以在全局记录 \(f_i\) 表示从 \(i\) 开始的最大上升子序列，然后可以发现支持前缀和，即 \(f_i - f_{mx} + a_{mx}\) ，直接 st 表求最大值。
- 在最大值后面的部分，可以发现以他结尾的最大上升子序列和原序列是一样的，因为区间的 \(\max\) 把他挡住了，因此我们可以记录 \(g_i\) 表示以 \(i\) 结尾的最大上升子序列，答案即为区间最大值。
- 因此我们可以用三个 st 表分别维护区间 \(\max a_i, \max f_i, \max g_i\) ，最终复杂度 \(O(n \log n + Q)\)