【题解】CF2043C Sums on Segments

题意概要

一个数组，最多有一个数的绝对值不是 \(1\)，求出所有可以得到的区间和。
思路

这里提供一个 数据结构优化查询前缀和最值 的做法。
最多有一个数的绝对值不是 \(1\)，那我们可以先忽略掉这个数（记该数下标为 \(x\)）。
剩下的数要么是 \(1\)，要么是 \(-1\)，所以我们扩展一个区间的时候，区间和的变化（或增或减）单位大小是 \(1\)。
因此，我们最后的值一定是至多 \(2\) 个连续整数区间：

• 一个是由 \(0\)（空区间） 扩展而来，并且扩展出的区间不包含 \(x\)。
  
• 一个是由 \(a_x\) 扩展而来。
  

首先考虑第一种区间，我们求出不包含 \(x\) 的所有区间和的最大值和最小值即可。
这个很明显是一个区间最值问题，但是这里涉及到区间和，所以我们先把原数组 \(a\) 进行前缀和操作转化为前缀和数组 \(pre\)。
然后，我们把前缀和数组 \(pre\) 存入 线段树 或 ST表 中维护区间前缀和最大值和最小值。
对于 \(x\) 左边的区间，我们从左到右枚举区间的左端点 \(i\)，查询 \(i\) 到 \(x\) 的区间前缀和最大值，减掉 \(pre_{i - 1}\)，就可以得到以 \(i\) 作为左端点的不包含 \(x\) 的所有区间的最大区间和。最小区间和同理。
对于 \(x\) 右边的区间，我们从左到右枚举区间的左端点 \(i\)，查询 \(i\) 到 \(n\) 的区间前缀和最大值，减掉 \(pre_{i - 1}\)，就可以得到以 \(i\) 作为左端点的不包含 \(x\) 的所有区间的最大区间和。最小区间和同理。
对于此类区间得到的结果取个并集，就是此类区间最后的结果。
然后是第二种区间，由 \(a_{x}\) 扩展而来。
此时这个区间一定包含 \(x\) ，因此，我们只需要以 \(x\) 为起点，分别向左向右扩展。
向左扩展变化的最小值加上向右扩展变化的最小值，就是此类区间的最小区间和。
向左扩展变化的最大值加上向右扩展变化的最大值，就是此类区间的最大区间和。
最后对两种区间求得的结果再取一个并集即可。
时间复杂度：\(O(n \log n)\)。
AC CODE

[code]// Problem: C. Sums on Segments// Contest: Codeforces - Educational Codeforces Round 173 (Rated for Div. 2)// URL: https://codeforces.com/contest/2043/problem/C// Memory Limit: 256 MB// Time Limit: 1000 ms// // Powered by CP Editor (https://cpeditor.org)#include #define int long long#define inf 2e18#define ull unsigned long long#define ls o  n;        for(int i = 1;i > a;        int ix = -1;        for(int i = 1;i