题解：P13963 [ICPC 2023 Nanjing R] 接雨水

· · 题解

Question

给定一个序列 a，支持单点加，查询

\sum_{i=1}^n\min(f_i,g_i)-a_i

其中 f_i = \max(a_1,a_2,\cdots,a_i),g_i = \max(a_i,a_{i+1},\cdots,a_n)。

Solution

考虑先把 -a_i 拆出去，那么答案就变为了维护 \sum_{i=1}^n\min(f_i,g_i)。

容易发现 f_i 是单调不降的，g_i 是单调不增的，所以一定存在一个 p 满足 [1,p] 中 f_i \le g_i，[p+1,n] 中 f_i\ge g_i，于是我们维护一个 f_i-g_i，然后在线段树上二分 0 的位置即可。

对于修改操作，我们发现每次只会增加，其实就是把一段区间的 f_i 全部改为 a_x+y，依然线段树二分找到 x 右边第一个满足 a_x+y>f_i 的点即可，g_i 的维护是一样的。

Code

/**
 *    author: luuia
 *    created: 2025.09.03 14:33:32
**/
#include<bits/stdc++.h>
using ll = long long;
#define For(i,j,k) for(int i = j;i <= k;i++)
#define Rep(i,j,k) for(int i = j;i >= k;i--)
using namespace std;
const int N = 1e6 + 10,p = 998244353;ll a[N],f[N],g[N];
struct seg{struct P{ll sf,sg,mxf,mng,mxg,mxd,tg1,tg2;}t[N];
    #define ls p << 1
    #define rs p << 1 | 1
    #define md (l + r >> 1)
    #define lc ls,l,md 
    #define rc rs,md + 1,r
    void psu(ll p){t[p] = {t[ls].sf + t[rs].sf,t[ls].sg + t[rs].sg,max(t[ls].mxf,t[rs].mxf),
        min(t[ls].mng,t[rs].mng),max(t[ls].mxg,t[rs].mxg),max(t[ls].mxd,t[rs].mxd),t[p].tg1,t[p].tg2};}
    void ad1(ll p,ll l,ll r,ll v){t[p].sf = v * (r - l + 1);
        t[p].mxf = v,t[p].mxd = v - t[p].mng,t[p].tg1 = v;
    }void ad2(ll p,ll l,ll r,ll v){t[p].sg = v * (r - l + 1);
        t[p].mng = t[p].mxg = v,t[p].mxd = t[p].mxf - v,t[p].tg2 = v;
    }void psd(ll p,ll l,ll r){if(l == r) return;
        if(~t[p].tg1) ad1(lc,t[p].tg1),ad1(rc,t[p].tg1),t[p].tg1 = -1;
        if(~t[p].tg2) ad2(lc,t[p].tg2),ad2(rc,t[p].tg2),t[p].tg2 = -1;
    }void bd(ll p,ll l,ll r){t[p].tg1 = t[p].tg2 = -1;if(l == r){
            t[p] = {f[l],g[l],f[l],g[l],g[l],f[l] - g[l],-1,-1};return;
        }bd(lc),bd(rc),psu(p);
    }void upd1(ll p,ll l,ll r,ll ql,ll qr,ll v){if(ql <= l && r <= qr){ad1(p,l,r,v);return;}
        psd(p,l,r);if(ql <= md) upd1(lc,ql,qr,v);if(qr > md) upd1(rc,ql,qr,v);psu(p);
    }void upd2(ll p,ll l,ll r,ll ql,ll qr,ll v){if(ql <= l && r <= qr){ad2(p,l,r,v);return;}
        psd(p,l,r);if(ql <= md) upd2(lc,ql,qr,v);if(qr > md) upd2(rc,ql,qr,v);psu(p);
    }ll fdf(ll p,ll l,ll r,ll x,ll v){if(r < x || t[p].mxf < v) return -1;if(l == r) return l;
        psd(p,l,r);ll o = -1;if(x <= md && ~(o = fdf(lc,x,v))) return o;return fdf(rc,x,v);
    }ll fdg(ll p,ll l,ll r,ll x,ll v){if(l > x || t[p].mxg < v) return -1;if(l == r) return l;
        psd(p,l,r);ll o = -1;if(x > md && ~(o = fdg(rc,x,v))) return o;return fdg(lc,x,v);
    }ll fdd(ll p,ll l,ll r){if(t[p].mxd <= 0) return -1;if(l == r) return l;psd(p,l,r);
        ll o = fdd(lc);if(~o) return o;return fdd(rc);
    }ll qry1(ll p,ll l,ll r,ll ql,ll qr){if(ql <= l && r <= qr) return t[p].mxf;
        psd(p,l,r);ll o = -1e18;if(ql <= md) _max(o,qry1(lc,ql,qr));if(qr > md) _max(o,qry1(rc,ql,qr));return o;
    }ll qry2(ll p,ll l,ll r,ll ql,ll qr){if(ql <= l && r <= qr) return t[p].mxg;
        psd(p,l,r);ll o = -1e18;if(ql <= md) _max(o,qry2(lc,ql,qr));if(qr > md) _max(o,qry2(rc,ql,qr));return o;
    }ll qry3(ll p,ll l,ll r,ll ql,ll qr){if(ql <= l && r <= qr) return t[p].sf;
        psd(p,l,r);ll o = 0;if(ql <= md) o += qry3(lc,ql,qr);if(qr > md) o += qry3(rc,ql,qr);return o;
    }ll qry4(ll p,ll l,ll r,ll ql,ll qr){if(ql <= l && r <= qr) return t[p].sg;
        psd(p,l,r);ll o = 0;if(ql <= md) o += qry4(lc,ql,qr);if(qr > md) o += qry4(rc,ql,qr);return o;
    }
}tr;void sol(){ll n,q,x,v,sm = 0,cr = 0;cin >> n;For(i,1,n) cin >> a[i],sm += a[i];
    For(i,1,n) _max(cr,a[i]),f[i] = cr;cr = 0;Rep(i,n,1) _max(cr,a[i]),g[i] = cr;
    tr.bd(1,1,n);cin >> q;while(q--){cin >> x >> v,a[x] += v,sm += v;
        ll o1 = max({0ll,x > 1 ? tr.qry1(1,1,n,1,x - 1) : (ll)-1e18,a[x]});
        ll po1 = tr.fdf(1,1,n,x,o1);if(po1 == -1) po1 = n + 1;
        if(po1 >= x + 1) tr.upd1(1,1,n,x,po1 - 1,o1);
        ll o2 = max({0ll,x < n ? tr.qry2(1,1,n,x + 1,n) : (ll)-1e18,a[x]});
        ll po2 = tr.fdg(1,1,n,x,o2);if(po2 == -1) po2 = 0;
        if(po2 + 1 <= x) tr.upd2(1,1,n,po2 + 1,x,o2);ll o = 0;
        ll po3 = tr.fdd(1,1,n) == -1 ? n : tr.fdd(1,1,n) - 1;
        if(po3 >= 1) o += tr.qry3(1,1,n,1,po3);if(po3 <= n - 1) o += tr.qry4(1,1,n,po3 + 1,n);
        cout << o - sm << '\n';
    }
}int main(){
    // freopen("input.in","r",stdin);
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    ll T;cin >> T;while(T--) sol();return 0;
}