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

#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;                                         	                
}