[ROIR 2025 Day 1] 酸雨 题解
FFTotoro
·
·
题解
先拆式子，由于 \max\{l_i,r_i\}=\max\limits_{j=l}^r h_j（即为 i 所在连通块 [l,r] 内的最大高度，记为 \mathrm{mx}_i），所以答案为 \sum\min\{l_i,r_i\}-h_i=\sum l_i+r_i-\max\{l_i,r_i\}-h_i=\sum l_i+\sum r_i-\sum h_i-\sum\mathrm{mx}_i。只需要对于这四个值分别维护。
为了方便找到编号为 $k$ 的区间，使用 `__gnu_pbds::tree` 来维护当前的所有连通块。
时间复杂度 $O(n\log n)$。
放代码：
```cpp
#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
using namespace std;
using namespace __gnu_pbds;
typedef pair<int,int> pii;
tree<pii,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> t;
main(){
ios::sync_with_stdio(false);
int n; cin>>n;
vector<int> h(n),cl(n,1),cr(n,1),mx(n),s(n);
vector<set<pii> > sl(n),sr(n);
iota(mx.begin(),mx.end(),0);
for(auto &i:h)cin>>i;
for(int i=0;i<n;i++){
t.insert(make_pair(i,i));
sl[i].emplace(h[i],i),sr[i].emplace(h[i],i);
} // 一些预处理
for(int i=1;i<n;i++){
int x; cin>>x,x--;
auto p=t.find_by_order(x);
auto [l1,r1]=*p; auto [l2,r2]=*next(p);
s[l1]+=s[l2];
while(!sl[l2].empty()){
if(int x=sl[l2].begin()->second;h[mx[l1]]>h[x])
s[l1]+=cl[x]*(h[mx[l1]]-h[x]),cl[mx[l1]]+=cl[x],cl[x]=0,sl[l2].erase(sl[l2].begin());
else break;
} // 维护 sum l[i]
while(!sr[l1].empty()){
if(int x=sr[l1].begin()->second;h[mx[l2]]>h[x])
s[l1]+=cr[x]*(h[mx[l2]]-h[x]),cr[mx[l2]]+=cr[x],cr[x]=0,sr[l1].erase(sr[l1].begin());
else break;
} // 维护 sum r[i]
if(sl[l1].size()<sl[l2].size())swap(sl[l1],sl[l2]);
if(sr[l1].size()<sr[l2].size())swap(sr[l1],sr[l2]);
sl[l1].merge(sl[l2]),sr[l1].merge(sr[l2]);
// 合并信息
if(h[mx[l2]]<h[mx[l1]])s[l1]-=(r2-l2+1)*(h[mx[l1]]-h[mx[l2]]);
else s[l1]-=(r1-l1+1)*(h[mx[l2]]-h[mx[l1]]),mx[l1]=mx[l2];
// 维护 sum mx[i]
t.erase(p=t.erase(p)),t.insert(make_pair(l1,r2));
cout<<s[l1]<<'\n';
}
return 0;
}
```