最大值

题目描述

现在有一个序列，有 $n$ 个数：$a_1,a_2,…,a_n$

假设有一个区间 $[l,r]$，那么它价值的计算方式：

$$k_{l,r}=|\sum_{i=l}^{r}{a_i}|$$

（其中 $|k|$ 代表 $k$ 的绝对值）。

现在找到一个区间使得 $k_{l,r}$ 最大，并输出这个最大值。

为了加强难度，有 $m$ 个询问，每个询问 $m_i$ 表示将整个区间加上 $m_i$ 后的结果。注意：每次的询问不会影响原序列（不会改变原序列的值）。

为了强制在线，每个 $m_i$ 都是经过加密的，其中

$$m_i=(m_i+lastans)\%(3\times n+1)-2\times n$$

（括号里的 $m_i$ 是读入的，等于号左边的是解密后的。）

注意数据范围，保证结果在 long long 范围内。

读入格式

$n,m$ 分别代表序列长度，$m$ 表示询问次数。

接下来一行 $n$ 个数，代表 $a_i$。

接下来 $m$ 行，代表 $m_i$。

输出格式

$m$ 行每行一个数，表示序列增加 $m_{i}$ 后的最大值 $k_{l,r}$。

样例 $1$

读入

latex

2 5
-5 -3 
6
1
5
3
0

输出

latex

4
6
8
8
14

样例 $2$

读入

latex

9 5
4 -3 -5 7 3 4 -4 -3 -6 
2
3
4
5
0

输出

latex

147
75
43
22
35

样例 $3$

读入

latex

6 8
-8477 -61819 -26079 86186 42236 15888 
8988
45179
23308
46883
57052
88266
438
48894

输出

latex

144277
144295
144286
144304
144313
144274
144298
144274

数据范围

$10$ 分：$n,m \le 100,|a_i| \le 1e4$

另 $20$ 分：$n,m \le 1e4,|a_i| \le 1e5$

另 $35$ 分：$n,m \le 2e5,|a_i| \le 2e5$

另 $25$ 分：$n,m \le 1e6,|a_i| \le 2e5$

最后 $10$ 分：$n,m \le 1e4,|a_i | \le 1e5,a_i$ 同号。

保证数据有梯度，保证正解不是数据结构。

题解

原题链接

为了方便直接获得一段区间的和，我们使用前缀。

那么区间的最大值即为：

$$k_{max}-k_{min}$$

但是在变化（整个序列增加 $m_i$）后：

$$k_{max},k_{min}$$

会改变。例如：

$1,-1,-5,-10,-3,9$

$$k_{max}=k_{2,5}$$

但是将整个序列增加 $3$：

$4,2,-2,-7,0,12$

$$k_{max}=k_{6,6}$$

所以我们要找到每次更新后的

$$k_{max},k_{min}$$

假设整个序列增加的值是 $m_i$，那么一段区间 $[l,r]$ 增加的值为：

$$(r-l+1)\times m_i$$

那么

$$(k_{l,r})^{'}=k_{l,r}+(r-l+1)\times m_i$$

其中 $r-l+1$ 和 $k_{l,r}$ 是常数，$m_i$ 是变量，所以整个式子是一个一次函数。

每次询问的增长都是所有元素同时增长，那么每个一次函数也都增长，增长的多少取决于斜率的大小（即 $r-l+1$）。

用凸包维护所有的一次函数，每次询问的 $m_i$ 增长后的最值在凸包上找。

上凸包和下凸包都是单调的，所以可以通过二分，来找到每次询问的 $m_i$ 在那条线段上，最后相减得到结果。

凸包代码

cpp

#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;
long long r_r(){
  long long x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
const long long o_o=2e6+10;
long long n,m,l,r,a,b,x;
long long s_i[o_o],m_x[o_o],m_a,m_n[o_o],m_i,l_a;
double u[o_o],v[o_o]; 
double c_j(long long a,long long b){//斜率（平均值取反） 
  return double(s_i[b]-s_i[a])/(a-b);
}
int main(){
    n=r_r();m=r_r();
    for(int i=1;i<=n;i++){
        s_i[i]=s_i[i-1]+r_r();//前缀和  
        
        //处理上下凸包 
        while(m_a&&c_j(i,m_x[m_a])<=c_j(i,m_x[m_a-1]))--m_a;
    m_x[++m_a]=i;
        while(m_i&&c_j(i,m_n[m_i])>=c_j(i,m_n[m_i-1]))--m_i;
    m_n[++m_i]=i;
    }
    //记录相邻两点的斜率 
    for(int i=1;i<=m_a;i++)u[i]=c_j(m_x[i],m_x[i-1]);
    for(int i=1;i<=m_i;i++)v[i]=c_j(m_n[i],m_n[i-1]);
    while(m--){
        x=(r_r()+l_a)%(3*n+1)-2*n;//解密 
        
        //二分找到 x 在那个线段上 
        if(x<=u[1])a=0;
        else {
          int l=1,r=m_a;
          while(l<=r){
            long long m_d=(l+r)>>1;         
              if(x>=u[m_d]){//二分查找 
                a=m_x[m_d];//记录 
          l=m_d+1;
        }else r=m_d-1;
      } 
    }
        if(x>=v[1])b=0;
        else {
          int l=1,r=m_i;
          while(l<=r){//二分查找 
            long long m_d=(l+r)>>1;
              if(x<=v[m_d]){
                b=m_n[m_d];//记录 
          l=m_d+1;
        }else r=m_d-1;
      }
    }
    //最值相减即为答案 
        printf("%lld\n",l_a=(a-b)*x+s_i[a]-s_i[b]);
    }
    return 0;
}