找回密码
 立即注册
首页 业界区 科技 【题解】CF2043C Sums on Segments

【题解】CF2043C Sums on Segments

劝匠注 6 天前
题意概要

一个数组,最多有一个数的绝对值不是 \(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
您需要登录后才可以回帖 登录 | 立即注册