「Codeforces 1107G」Vasya and Maximum Profit

发表于 | | 阅读次数:
字数统计: 288 字

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%