积水 题解
Anemones
·
·
个人记录
不难发现最终第 i 个位置积水的高度为
发现改变一个位置有两种情况：
1. 将该位置调高减少积水
2. 将该位置调低放走别的位置的积水
对于情况 1，非常容易处理，选择的必然是积水高度与当前位置高度相差最大的位置。
对于情况 2，稍微麻烦一些。
由于要“放水”改动的位置肯定在前缀 $\max$ 上或者后缀 $\max$ 上。
假设枚举的位置是 $i$，且 $i$ 位于前缀 $\max$ 上。
那么修改后的高度一定会是 $\max_{j=1}^{i-1} a_j$。
感性理解一下，就是说比这个值小，就是凹下去了一块，不优。
比这个值大，后面的积水可能不能完全放掉，并不会更优。
于是枚举这些点，暴力计算放掉的水即可。
将一个位置改低，只会影响一段区间。
修改不同的位置，这些影响的区间不会重叠。
因此，时间复杂度为 $O(n)$。
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[1020000],pmx[1020000],smx[1020000];
bool tpre[1020000],tsuf[1020000];
void solve() {
cin>>n;ll tans=0,ans;int tmax=0;
for(int i=0; i<=n+1; ++i)tpre[i]=tsuf[i]=0;
for(int i=1; i<=n; ++i)cin>>a[i];
pmx[0]=smx[n+1]=-2e9;
for(int i=1; i<=n; ++i)tpre[i]=pmx[i-1]<a[i],pmx[i]=max(pmx[i-1],a[i]);
for(int i=n; i; --i)tsuf[i]=smx[i+1]<a[i],smx[i]=max(smx[i+1],a[i]);
for(int i=1; i<=n; tans=max(tans,ans))if(tpre[i])
for(tmax=pmx[i-1],ans=0,++i; !tpre[i]&&i<=n; ++i)tmax=max(tmax,a[i]),ans+=min(pmx[i],smx[i])-min(tmax,smx[i]);
for(int i=n; i>0; tans=max(tans,ans))
for(tmax=smx[i+1],ans=0,--i; !tsuf[i]&&i; --i)tmax=max(tmax,a[i]),ans+=min(pmx[i],smx[i])-min(tmax,pmx[i]);
tans=-tans;
for(int i=1; i<=n; ++i)tans=min(tans,a[i]-min(pmx[i],smx[i])+0ll);
for(int i=1; i<=n; ++i)tans+=min(pmx[i],smx[i])-a[i];
cout<<tans<<'\n';
}
int main() {
int T;ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>T;while(T--)solve();
}
```