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

· · 题解

记 mx=\max(a_i)，p 为第一个 a_p=mx，不难发现 f_i 从右往左单调递增，遇到 mx 后不变，g_i 同理，? 难发现 \min(f_i,g_i)=f_i+g_i-mx。

应为 g_i 和 f_i 之中有一个或两个最大值。

维护 f,g 分别是往前往后取 \max。

然后吉老师线段树就好了。

然后珂朵莉树也是复杂度也是对的，每个元素被加进来一次，删除一次，总更新次数是 O(n+q) 的，总复杂度是 O((n+q)\log n)。

选更好写的珂朵莉树。

#include<bits/stdc++.h>
#define N 100005
#define gcd __gcd
#define int long long
#define inf LONG_LONG_MAX
#define fr first
#define se second
#define V 1000000000
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
#define IT set<node>::iterator 
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
int n,a[N],T,q,x,v;
inline int read()
{
    int x=0,f=1;
    char ch=gc;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            f=-1;
        ch=gc;
    }
    while(ch>='0' && ch<='9')
        x=x*10+ch-'0',ch=gc;
    return x*f;
}
struct node{
    int l,r,v;
    node(int L,int R=0,int w=0):l(L),r(R),v(w){}
    inline bool operator <(const node &o)const{return l<o.l;}
};
struct ODT{
    int sum=0;
    set<node>s;
    inline void clear(){s.clear();sum=0;s.insert(node(1,n,0));}
    inline IT split(int pos){
        IT it=s.lower_bound(node(pos));
        if(it!=s.end()&&pos==it->l) return it;
        --it;
        int l=it->l,r=it->r,v=it->v;s.erase(it);
        s.insert(node(l,pos-1,v));
        return s.insert(node(pos,r,v)).fr;
    }
    inline void chkmx(int x,int v){
        IT it=split(x),i;
        for(i=it;i!=s.end();++i){
            if(i->v>=v) break;
            sum+=(v-i->v)*(i->r-i->l+1);
        }
        int r;
        if(i==s.end()) r=n;
        else r=i->l-1;
        if(v>=it->v){
            s.erase(it,i);
            s.insert(node(x,r,v));
        }
    }
}f,g;
inline void solve(){
    n=rd;int sum=0,mx=0;f.clear();g.clear();
    for(int i=1;i<=n;i++) a[i]=rd,sum+=a[i],mx=max(mx,a[i]);
    for(int i=1;i<=n;i++){g.chkmx(n-i+1,a[i]);f.chkmx(i,a[i]);}
    q=rd;
    for(int i=1;i<=q;i++){
        x=rd,v=rd;a[x]+=v;mx=max(mx,a[x]);sum+=v;  
        f.chkmx(x,a[x]);g.chkmx(n-x+1,a[x]);
        cout<<f.sum+g.sum-mx*n-sum<<'\n';
    }
}
signed main(){
//  freopen("dat.in","r",stdin);
//  freopen("dat.out","w",stdout);                       
    T=rd;                                
    while(T--) solve();                                                                                
    return 0;                                                           
}