「Codeforces 1107G」Vasya and Maximum Profit

Description

题目链接:Codeforces 1107G

Vasya 打算举办一场比赛,他有 $n$ 个题目可供选择,标号为 $1$ 到 $n$。第 $i$ 道题的难度为 $d_i$,保证题目的难度递增,且两两不同。添加第 $i$ 道题需要向其作者支付 $c_i$ 的钱,每道题会使 Vasya 获得 $a$ 的钱。

他选择的题目一定是一个连续的子段。

所以比赛的总收益计算如下:

  • 如果 Vasya 添加了第 $i$ 道题目,那么他需要支付 $c_i$ 的钱。
  • 对于比赛中的每道题目,Vasya 会得到 $a$ 的钱。
  • 令 $\text{gap}(l,r)=\max_{l\le i<r} (d_{i+1}-d_i)^2$。如果 Vasya 将第 $l$ 到第 $r$ 道题目添加到了比赛中,他还需要支付 $\text{gap}(l,r)$ 的钱。特殊的,当 $l=r$ 时,$\text{gap}(l,r)=0$。

请你计算 Vasya 举办这场比赛最多能获得的收益。

数据范围:$1\le n\le 3\times 10^5$,$1\le a,d_i,c_i\le 10^9$,$d_i<d_{i+1}$


Solution

首先我们将所求用数学式子表示出来:

我们先考虑一个简单版本:没有 $d_i$ 的限制。那么本题就变成了一个裸的最大子段和

接下来进一步推广:如果 $\max_{i\le i<r}(d_{i+1}-d_i)^2$ 的值确定了,那么依旧是一个最大子段和的问题。

至此,我们已经可以发现:只要确定每个 $(d_{i+1}-d_i)^2​$ 的贡献区间范围,那么就转化成了简单问题了(最大子段和可以通过线段树维护)。

所以,现在的问题就是如何求 $d_{i+1}-d_i$ 的贡献范围。记 $dif_i=d_{i+1}-d_i(1\le i<n)$,那么就是求一段区间 $[l,r]$ 满足 $dif_i$ 是区间内的最大值。这个模型可以维护一个递减的单调栈解决。注意求出的区间 $[l,r]$ 在原序列中应该是 $[l,r+1]$(因为 $dif_i=d_{i+1}-d_i$)。

注意 $l=r$ 的情况:此时不存在 $dif_i$,因此要特殊处理!

时间复杂度:$O(n\log n)$


Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <cstdio>
#include <algorithm>
#define lson p<<1
#define rson p<<1|1
typedef long long LL;

const int N=3e5+5;
const LL INF=1LL<<60;
int n,A,a[N],d[N],l[N],r[N];
struct Stack {
int val,idx;
Stack(int _val=0,int _idx=0) {val=_val,idx=_idx;}
} st[N];
struct node {
LL lmx,rmx,sum,ret;
node(LL _lmx=-INF,LL _rmx=-INF,LL _sum=-INF,LL _ret=-INF) {
lmx=_lmx,rmx=_rmx,sum=_sum,ret=_ret;
}
} seg[N<<2];

node merge(node x,node y) {
if(x.sum==-INF) return y;
if(y.sum==-INF) return x;
node ans;
ans.lmx=std::max(x.lmx,x.sum+y.lmx);
ans.rmx=std::max(y.rmx,y.sum+x.rmx);
ans.sum=x.sum+y.sum;
ans.ret=std::max(x.rmx+y.lmx,std::max(x.ret,y.ret));
return ans;
}
void pushup(int p) {
seg[p]=merge(seg[lson],seg[rson]);
}
void build(int p,int l,int r) {
if(l==r) {
seg[p]=node(a[l],a[l],a[l],a[l]);
return;
}
int mid=(l+r)>>1;
build(lson,l,mid),build(rson,mid+1,r);
pushup(p);
}
node query(int x,int y,int p,int l,int r) {
if(x<=l&&r<=y) return seg[p];
int mid=(l+r)>>1;
node L,R;
if(x<=mid) L=query(x,y,lson,l,mid);
if(mid<y) R=query(x,y,rson,mid+1,r);
return merge(L,R);
}
void solve(int n) {
int tp;
st[tp=1]=Stack(2e9,0);
for(int i=1;i<=n;++i) {
while(st[tp].val<=d[i]) --tp;
l[i]=st[tp].idx+1;
st[++tp]=Stack(d[i],i);
}
st[tp=1]=Stack(2e9,n+1);
for(int i=n;i>=1;--i) {
while(st[tp].val<=d[i]) --tp;
r[i]=st[tp].idx-1;
st[++tp]=Stack(d[i],i);
}
}
int main() {
scanf("%d%d",&n,&A);
long long ans=0;
for(int i=1;i<=n;++i) {
scanf("%d%d",&d[i],&a[i]);
a[i]=A-a[i],ans=std::max(ans,1LL*a[i]);
}
for(int i=1;i<n;++i) d[i]=d[i+1]-d[i];
solve(n-1);
build(1,1,n);
for(int i=1;i<n;++i) {
ans=std::max(ans,query(l[i],r[i]+1,1,1,n).ret-1LL*d[i]*d[i]);
}
printf("%lld\n",ans);
return 0;
}
0%