自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 23:09:35，当前版本为作者最后更新于2025-02-17 10:11:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先拆式子，由于 $\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$。只需要对于这四个值分别维护。

$\sum h_i$ 直接计算，$\sum\mathrm{mx}_i$ 可以在合并连通块 $x,y$ 时，考虑将 $\mathrm{mx}_x$ 与 $\mathrm{mx}_y$ 中的较小值增大到较大值的贡献即可。对于 $\sum l_i$ 的维护（$\sum r_i$ 同理），注意到 $l_i$ 的值在操作过程中是递增的，所以将 $i$ 的贡献挂在 $l_i$ 对应的位置 $j$ 上（即某个 $j$ 使得 $h_j=l_i$），于是我们只需维护这些 $j$；合并两个连通块时，考虑靠左的连通块的 $h$ 最大值，将靠右的连通块中 $h_j$ 小于等于该最大值的 $j$ 的贡献转移到最大值上。这些过程都可以使用启发式合并维护。更多细节参考代码；代码中将连通块的信息挂在左端点上。

为了方便找到编号为 $k$ 的区间，使用 __gnu_pbds::tree 来维护当前的所有连通块。

时间复杂度 $O(n\log n)$。

放代码：

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