思路与算法

一个连续标记段长度为k时，内部全标记子区间共有k(k+1)/2个，因此其贡献为该数减去段内T之和。记S_i为原数组前缀和，F_i为前i个位置的最大分数，H_i为从i到n的最大分数。由最后一段[l+1,i]得到F_i=max(F_{i-1},max_{l<i}(F_l+S_l+l(l-1)/2-li)+i(i+1)/2-S_i)，把括号视为斜率-l、截距F_l+S_l+l(l-1)/2的直线，按l递增加入凸包并查询i；后缀对逆序数组同样计算。再设G_p为原序列中强制标记p时的最大分数。令A_l=F_l+S_l+l(l-1)/2，B_r=H_{r+1}-S_r+r(r+1)/2，则G_p=max_{l<p<=r}(A_l+B_r-lr)。在端点0..n上分治：对跨中点的l<=mid<r，先将所有右端r建成直线-rx+B_r，求每个l的V_l=A_l+max_r(B_r-lr)，在p<=mid侧对l<p取前缀最大值更新G_p；再把左端l建成直线-lx+A_l，求每个r的W_r=B_r+max_l(A_l-lr)，在p>=mid+1侧取r>=p的后缀最大值更新G_p。每层线斜率和查询次序均单调，可用凸包队首指针。查询修改T_p为X后，不标记p的答案为F_{p-1}+H_{p+1}；标记p的每个方案分数都统一增加T_p-X，故答案为两者与G_p+T_p-X的最大值。

正确性说明

各最大连续标记段贡献可相加，故由最后一段枚举可覆盖任意最优前缀方案。F_l和后接标记段若相邻同时被标记，分开计算只是遗漏跨两段的非负子区间贡献，所得候选不会高于真实可行方案；反过来用某个最优方案的最后最大标记段，候选至少达到该最优值，故这个允许相邻划分的递推仍与真实最优值相等。强制标记p的G同理：任意候选由前缀最优、包含p的段和后缀最优组成，真实标记方案分数至少为候选；取真实最优方案包含p的最大段，则相应候选至少达到最优值，夹逼得到G公式精确。每一对端点l<r恰在一个分治结点首次跨中点，该处p在左半时所有右端均满足r>=p，只需对l<p取前缀最大；p在右半时所有左端均满足l<p，只需对r>=p取后缀最大。因此全部区间对其覆盖位置的最大贡献都被更新且没有额外不可行候选。凸包仅删去永不成为最大值的直线，交叉乘法比较保持精确。最后每个方案恰属于p选或不选一类，且仅p的成本变化，所以两类闭式取最大正确，询问互不污染。

复杂度

前缀和及全部结果数组初始化O(n)。前后缀DP各加入n条斜率单调直线，每条最多入栈/出栈一次，查询使用凸包二分O(log n)，因此合计O(n log n)。端点分治每一层建两次凸包、单调查询和前后缀扫描总O(n)，深度O(log n)，故G预处理O(n log n)。每个修改询问O(1)，总时间O(n log n+m)，包括读入输出；空间O(n)，各层临时凸包在递归前释放，未保存n²个端点对。分数、前缀和与直线取值使用int64，凸包交叉乘积使用__int128，避免浮点误差。

易错点

所求子区间数是每个连续全标记段的k(k+1)/2，不能只计一个段。允许空标记方案，答案至少0。询问独立，不能直接覆盖原T；修改p被选时统一加原T_p-X。G端点条件为l<p<=r；分治中p=mid+1由右侧后缀扫描负责，不能漏掉。斜率按端点递增而递减，单调查询必须按坐标递减推进凸包指针。中间直线截距可为负，不能把初始G误设0；N1也须算强制选择分数1-T_1。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Line {
    ll m, b;
    ll at(ll x) const {
        return m * x + b;
    }
};
struct Hull {
    vector<Line> a;
    size_t head = 0;
    void add(ll m, ll b) {
        Line c{m, b};
        while (a.size() >= 2) {
            Line x = a[a.size() - 2], y = a.back();
            if ((__int128)(y.b - x.b) * (y.m - c.m) <= (__int128)(c.b - y.b) * (x.m - y.m))
                a.pop_back();
            else
                break;
        }
        a.push_back(c);
    }
    ll binary(ll x) const {
        int l = 0, r = (int)a.size() - 1;
        while (l < r) {
            int m = (l + r) / 2;
            if (a[m].at(x) <= a[m + 1].at(x))
                l = m + 1;
            else
                r = m;
        }
        return a[l].at(x);
    }
    ll monotone(ll x) {
        while (head + 1 < a.size() && a[head].at(x) <= a[head + 1].at(x))
            head++;
        return a[head].at(x);
    }
};
vector<ll> prefix(const vector<ll> &t) {
    int n = t.size() - 1;
    vector<ll> s(n + 1), p(n + 1);
    Hull h;
    h.add(0, 0);
    for (ll i = 1; i <= n; i++) {
        s[i] = s[i - 1] + t[i];
        p[i] = max(p[i - 1], i * (i + 1) / 2 - s[i] + h.binary(i));
        h.add(-i, p[i] + s[i] + i * (i - 1) / 2);
    }
    return p;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> t(n + 1), sum(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> t[i];
        sum[i] = sum[i - 1] + t[i];
    }
    vector<ll> pre = prefix(t), rev(n + 1);
    for (int i = 1; i <= n; i++)
        rev[i] = t[n - i + 1];
    auto rp = prefix(rev);
    vector<ll> suf(n + 2);
    for (int i = 1; i <= n; i++)
        suf[i] = rp[n - i + 1];
    vector<ll> A(n + 1), B(n + 1), G(n + 1, LLONG_MIN / 4);
    for (ll i = 0; i <= n; i++) {
        A[i] = pre[i] + sum[i] + i * (i - 1) / 2;
        B[i] = suf[i + 1] - sum[i] + i * (i + 1) / 2;
    }
    function<void(int, int)> solve = [&](int L, int R) {
        if (L == R)
            return;
        int mid = (L + R) / 2;
        {
            Hull h;
            for (int r = mid + 1; r <= R; r++)
                h.add(-r, B[r]);
            vector<ll> v(mid - L + 1);
            for (int l = mid; l >= L; l--)
                v[l - L] = A[l] + h.monotone(l);
            ll best = LLONG_MIN / 4;
            for (int p = L + 1; p <= mid; p++) {
                best = max(best, v[p - 1 - L]);
                G[p] = max(G[p], best);
            }
            Hull left;
            for (int l = L; l <= mid; l++)
                left.add(-l, A[l]);
            best = LLONG_MIN / 4;
            for (int p = R; p >= mid + 1; p--) {
                best = max(best, B[p] + left.monotone(p));
                G[p] = max(G[p], best);
            }
        }
        solve(L, mid);
        solve(mid + 1, R);
    };
    solve(0, n);
    int m;
    cin >> m;
    while (m--) {
        int p;
        ll x;
        cin >> p >> x;
        cout << max(pre[p - 1] + suf[p + 1], G[p] + t[p] - x) << '\n';
    }
}