CodeForces 1107 - G Vasya and Maximum Profit 线段树

题目传送门

题解：

枚举 r 的位置。

线段树每个叶子节点存的是对应的位置到当前位置的价值。

每次往右边移动一个r的话，那么改变的信息有2个信息：

1. sum(a-ci)

2.gap(l, r)

对于第一个东西，我们直接对[1,r]区间内的所有值都加上a-ci就好了。

对于第2个修改的值，首先要明白的是，这个值只会对[1,r-1]内的值存在影响。

并且可以发现，每一段区间的这个gap值每次更新完之后是从左到右递减的，所以我们可以用一个单调栈来维护这个gap值。

代码：

/*

code by: zstu wxk

time: 2019/01/31

*/

#include<bits/stdc++.h>

using namespace std;

#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);

#define LL long long

#define ULL unsigned LL

#define fi first

#define se second

#define pb push_back

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define lch(x) tr[x].son[0]

#define rch(x) tr[x].son[1]

#define max3(a,b,c) max(a,max(b,c))

#define min3(a,b,c) min(a,min(b,c))

typedef pair<int,int> pll;

const int inf = 0x3f3f3f3f;

const int _inf = 0xc0c0c0c0;

const LL INF = 0x3f3f3f3f3f3f3f3f;

const LL _INF = 0xc0c0c0c0c0c0c0c0;

const LL mod =  (int)1e9+;

const int N = 3e5 + ;

int Wa(){return rand()%;}

void Hack(int n){srand(time());int hack = ;for(int j = ; j <= n; ++j)hack += Wa();if(hack == n)puts("OH No!");}

int n, a;

int c[N], d[N];

LL Mx[N<<], lz[N<<];

void PushDown(int rt){

    if(lz[rt]){

        Mx[rt<<] += lz[rt];

        Mx[rt<<|] += lz[rt];

        lz[rt<<] += lz[rt];

        lz[rt<<|] += lz[rt];

        lz[rt] = ;

    }

}

void PushUp(int rt){

    Mx[rt] = max(Mx[rt<<], Mx[rt<<|]);

}

void Update(int L, int R, LL C, int l, int r, int rt){

    if(L <= l && r <= R){

        Mx[rt] += C;

        lz[rt] += C;

        return ;

    }

    int m = l+r >> ;

    PushDown(rt);

    if(L <= m) Update(L, R, C, lson);

    if(m < R)  Update(L, R, C, rson);

    PushUp(rt);

}

struct Node{

    int l, r;

    LL v;

}B[N];

stack<int> id;

void Ac(){

    for(int i = ; i <= n; ++i){

        scanf("%d%d", &d[i], &c[i]);

        c[i] = a - c[i];

    }

    LL ans = max(, c[]);

    Update(,,c[],,n,);

    for(int i = ; i <= n; ++i){

        Update(,i,c[i],,n,);

        B[i].l = B[i].r = i-;

        B[i].v = 1ll * (d[i] - d[i-]) * (d[i] - d[i-]);

        while(!id.empty() && B[id.top()].v < B[i].v){

            int x = id.top(); id.pop();

            Update(B[x].l, B[x].r, B[x].v, , n, );

            B[i].l = B[x].l;

        }

        Update(B[i].l, B[i].r, -B[i].v, , n, );

        id.push(i);

        ans = max(ans, Mx[]);

    }

    printf("%I64d\n", ans);

}

int main(){

    while(~scanf("%d%d", &n, &a)){

        Ac();

    }

    return ;

}