Language: C++


Copy
Copy
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ld, ld> pdd;
 
#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
 
struct Line{
    ll a;
    ll b;
    ll p;
};
 
const ll inf = (ll)4e18;
 
struct cht{
    deque<Line> hull;
    void clean(){
        hull.clear();
    }
    ll div(ll x, ll y){
        return (x/y - (x%y != 0 && (x ^ y) < 0));
    }
    void push(Line T){
        int m;
        ll cx;
        while(hull.size() >= 2){
            m = hull.size();
            cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
            if(hull[m - 2].p >= cx){
                hull.pop_back();
            }
            else{
                break;
            }
        }
        if(hull.size() >= 1){
            m = hull.size();
            cx = div(hull[m - 1].b - T.b, T.a - hull[m - 1].a);
            hull[m - 1].p = cx;
        }
        hull.push_back(T);
    }
    ll query(ll x){
        int l = 0;
        int r = (int)hull.size() - 1;
        int md;
        while(l < r){
            md = (l + r) / 2;
            if(hull[md].p < x)
                l = md + 1;
            else
                r = md;
        }
        return hull[r].a * x + hull[r].b;
    }
};
 
const int N = (int)3e5 + 9;
 
ll t[N];
ll f[N];
 
ll li[N];
ll ri[N];
ll inc[N];
 
cht cur;
 
void solve(int L, int R){
    if(L == R){
        return;
    }
    int mid = (L + R) / 2;
    solve(L, mid);
    solve(mid + 1, R);
    cur.clean();
    ll p;
    ll mx;
    for(ll i = L; i <= mid ; i ++ ){
        p = i - 1;
        cur.push({p,p * (p - 1)/2ll + f[p] + li[max(0ll, i - 2)],inf});
    }
    mx = -inf;
    for(ll i = R; i >= mid + 1; i -- ){
        mx = max(mx, cur.query(-i) + i * (i + 1) / 2ll + ri[i + 2] - f[i]);
        inc[i] = max(inc[i], mx);
    }
    cur.clean();
    for(ll i = R; i >= mid + 1; i -- ){
        cur.push({-i,i * (i + 1) / 2ll + ri[i + 2] - f[i] ,inf});
    }
    mx = -inf;
    for(ll i = L ;i <= mid ;i ++ ){
        p = i - 1;
        mx = max(mx, cur.query(p) + p * (p - 1) / 2ll + li[max(0ll, i - 2)] + f[p]);
        inc[i] = max(inc[i], mx);
    }
    cur.clean();
}
 
int main(){
    fastIO;
    int n;
    cin >> n;
    for(int i = 1; i <= n; i ++ ){
        cin >> t[i];
        f[i] = t[i];
        f[i] += f[i - 1];
    }
    for(int i = 0; i < N; i ++ )
        li[i] = -inf, ri[i] = -inf, inc[i] = -inf;
    li[0] = 0;
    ri[n + 1] = 0;
    ri[n + 2] = 0;
    ll p;
    
    for(ll i = 1 ; i <= n; i++ ){
        p = i - 1;
        li[i] = li[i - 1];
        cur.push({p, p * (p - 1)/2ll + f[p] + li[max(0ll, i - 2)], inf});
        li[i] = max(li[i], cur.query(-i) + i * (i + 1) / 2ll - f[i]); 
    }
    cur.clean();
    for(ll i = n; i >= 1; i -- ){
        p = i - 1;
        ri[i] = ri[i + 1];
        cur.push({-i, i * (i + 1)/2ll - f[i] + ri[i + 2], inf});
        ri[i] = max(ri[i], cur.query(p) + p * (p - 1) / 2ll + f[p]);
    }
    cur.clean();
    solve(1, n);
    int q;
    cin >> q;
    ll res;
    int id;
    ll x;
    for(int i = 0 ;i < q; i ++ ){
        cin >> id >> x;
        cout << max(inc[id] + (t[id] - x), li[id - 1] + ri[id + 1]) << "\n";
    }
    return 0;
}

Compiler output:
a.cc:2:1: error: 'Copy' does not name a type
    2 | Copy
      | ^~~~