最大值


题目描述

现在有一个序列,有 n 个数:a1,a2,,an

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

kl,r=|i=lrai|

(其中 |k| 代表 k 的绝对值)。

现在找到一个区间使得 kl,r 最大,并输出这个最大值。

为了加强难度,有 m 个询问,每个询问 mi 表示将整个区间加上 mi 后的结果。注意:每次的询问不会影响原序列(不会改变原序列的值)。

为了强制在线,每个 mi 都是经过加密的,其中

mi=(mi+lastans)%(3×n+1)2×n

(括号里的 mi 是读入的,等于号左边的是解密后的。)

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

读入格式

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

接下来一行 n 个数,代表 ai

接下来 m 行,代表 mi

输出格式

m 行每行一个数,表示序列增加 mi 后的最大值 kl,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,m100,|ai|1e4

20 分:n,m1e4,|ai|1e5

35 分:n,m2e5,|ai|2e5

25 分:n,m1e6,|ai|2e5

最后 10 分:n,m1e4,|ai|1e5,ai 同号。

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

题解

原题链接

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

那么区间的最大值即为:

kmaxkmin

但是在变化(整个序列增加 mi)后:

kmax,kmin

会改变。例如:

1,1,5,10,3,9

kmax=k2,5

但是将整个序列增加 3

4,2,2,7,0,12

kmax=k6,6

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

kmax,kmin

假设整个序列增加的值是 mi,那么一段区间 [l,r] 增加的值为:

(rl+1)×mi

那么

(kl,r)=kl,r+(rl+1)×mi

其中 rl+1kl,r 是常数,mi 是变量,所以整个式子是一个一次函数。

每次询问的增长都是所有元素同时增长,那么每个一次函数也都增长,增长的多少取决于斜率的大小(即 rl+1)。

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

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

凸包代码

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;
}

文章作者: 王大神——A001
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 王大神——A001 !