8113. 【2022.10.7联考noip模拟】Talulah
题意
给定长度为 \(n\) 的排列 \(p\)，定义集合 \(S_i = \{j \mid j \ge i \land \max_{k \in [i,j]} p_k = p_j\}\)。
给定 \(q\) 次询问 \(l,r\)，求 \(\sum_{x,y \in [l,r]} |S_x \cap S_y|\)。
\(n,q \le 2.5 \times 10^5\)
GMOJ
8081.【2024年SD省队集训 day2】反转了 (flip)
题意
给定长度为 \(N\) 的数组 \(A\)，定义 \(S_0 = 0\)，\(S_i = \sum_{j=1}^i A_j(i \in [1,N])\)。
对 \(K \in [0,N]\)，求解：
- 至多反转 \(K\) 个元素的符号，求 \(\max_{i \in [0,N]} {S_i}\) 的最大值。