题解：P13963 [ICPC 2023 Nanjing R] 接雨水
腼腆的立辉
·
·
题解
提供一个不需要数据结构就可以解决的方法。
思路
考虑给这个式子化简，我们知道 \max(x,y)=x+y-\min(x,y)。
所以可以给这个式子化简成：
\sum_{i=1}^n f_i +\sum_{i=1}^n g_i - n\times\max_{i=1}^n a_i -\sum_{i=1}^{n} a_i
后两项很好维护，我们把重点放到 f 和 g 的求和上。
我们先考虑 f，g 就可以把 a 反过来一样的方法求出。
注意到一个数 a_i 的贡献可能是一个区间，直到下一个比它大的数出现（如果前面有比它大的，那它暂时不会产生贡献）。
那么我们可以考虑给 f 维护集合 s，每个存 \{id,val\} 表示一段相同数值的起始点和相同的数值。
拿出相邻的两个元素，记作 \{id_1,val_1\} 和 \{id_2,val_2\}，显然 [id_1,id_2-1] 这个区间内的 f 值全部是 val_1。
考虑目前要在 a_x 加上 v。
先找到 x 所在的段，即最后一个 id \le x 的段，如果现在的 a_x+v 还没有超过所在段的 val，那么不会影响最大值。
如果大于，说明影响到了最大值，需要改动。
说明在 x 在这个段的起点之后，我们先减去这整个段的全部贡献，再加上这个段被斩断后的贡献。
此时加入 \{x,a_x+v\} 这个段，这个段可能后面会有 val 比其小的，要删去。
说明在 x 在这个段的起点，那这个段就直接没了，换成了 \{x,a_x+v\}。减去原来的贡献，再把后面小于新段的删掉，再加上贡献就好。
因为 $g$ 是单调不增的，和 f 的单调不减不一样，但反转后就一样了。
---
以上是思路，不过具体细节尚多，详细的见代码与注释。
时间复杂度 $\text{O}((n+q)\log (n+q))$。
## 代码
```
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1000000;
const int INF=1e18;
int n,a[MAXN+5];
int maxx,sum;
int sum_f,sum_rev;
// f 的和，g 的和
set<pair<int,int>> sf,srev;
// 计算 set 中 it 指向的这个段的贡献
int solve(set<pair<int,int>>& s, set<pair<int,int>>::iterator it, int n)
{
auto nxt=next(it); // 找到 it 下一个迭代器
int r=(nxt==s.end()?n:(*nxt).first-1);
//取迭代器的 id，如果 it 本身就是最后一个那就是 n
return (*it).second*(r-(*it).first+1);
// val*(r-id+1)
}
// 维护一个前缀最大值 set：位置 pos 的值变成了 val，更新 tot
void change(set<pair<int,int>>& s,int pos,int val,int n,int& tot)
{
// 找到 pos 所在的段
auto it=s.upper_bound({pos,INF});
it--; //先找到第一个大于的，再减一就是最后一个小于等于的
int st=(*it).first; //段起点
int old_val=(*it).second; //旧的 val 值
if(val<=old_val)
{
return; //没超过当前前缀最大值，不变
}
if(st<pos) //如果 pos 在 st 之后
{
// pos 在段内部（不是段起点）
tot-=solve(s,it,n); // 减掉旧段的贡献
tot+=old_val*(pos-st); // 旧段缩短为 st~pos-1，补回
auto now=s.insert({pos,val}); // 插入新段
auto new_it=now.first; // 新的迭代器
auto nxt=next(new_it); // 找到新迭代器的下一位，往后遍历寻找有没有需要更新的
while(nxt!=s.end() && (*nxt).second<=val) // 删掉后面值不够大的段
{
tot-=solve(s,nxt,n);//减去这一段的贡献
nxt=s.erase(nxt); //并删除
}
tot+=solve(s,new_it,n); // 加上新段的贡献
}
else
{
// pos 正好是某段的起点
tot-=solve(s,it,n); // 减掉旧段全部贡献
s.erase(it); // 删掉旧段
auto now=s.insert({pos,val}); // 插入新段
//与 st<pos 部分同理
auto new_it=now.first;
auto nxt=next(new_it);
while(nxt!=s.end()&&(*nxt).second<=val) // 删掉后面值不够大的
{
tot-=solve(s,nxt,n);
nxt=s.erase(nxt);
}
tot+=solve(s,new_it,n); // 加上新段的贡献
}
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
cin>>n;
sf.clear();
srev.clear();
maxx=sum=sum_f=sum_rev=0;
for(int i=1;i<=n;i++)
{
cin>>a[i];
sum+=a[i];
maxx=max(maxx,a[i]);
}
// 建 sf：从左往右扫，前缀最大值变化时插入新段
int res=0;
for(int i=1;i<=n;i++)
{
res=max(res,a[i]);
if(sf.empty() || (*(sf.rbegin())).second!=res)
{//如果空，或者上一个最大值不等于自己，说明开始了一个新段
sf.insert({i,res});
}
}
for(auto it=sf.begin();it!=sf.end();it++)
{
sum_f+=solve(sf,it,n);//记录 f 的和
}
// 建 srev：反转数组的前缀最大值(其实就是 g 数组的集合)
// 原数组 a[i] 反转后 b[k]=a[n-k+1]
// g[i]=max(a[i..n])=max(b[n-i+1..n])=fb[n-i+1]（fb 是 b 的前缀最大值）
// 所以 sum_g = sum_rev
res=0;
for(int i=n;i>=1;i--)
{
res=max(res,a[i]); // 从右往左扫，相当于反转数组从左往右
if(srev.empty() || (*(srev.rbegin())).second!=res)
{
srev.insert({n-i+1,res}); // 反转数组中的位置
}
}
for(auto it=srev.begin();it!=srev.end();it++)
{
sum_rev+=solve(srev,it,n); // 同理
}
int q;
cin>>q;
while(q--)
{
int x,v;
cin>>x>>v;
a[x]+=v;
maxx=max(a[x],maxx);
sum+=v;
// 更新 sf（原数组位置 x）
change(sf,x,a[x],n,sum_f);
// 更新 srev（反转数组位置 n-x+1）
change(srev,n-x+1,a[x],n,sum_rev);
int ans=sum_f+sum_rev-n*maxx-sum;//按公式算
cout<<ans<<'\n';
}
}
return 0;
}
```