[NERC2023] Great City Saint Petersburg 题解

FFTotoro · 2025-05-09 11:45:33 · 题解

跟 [ROIR 2025 Day 1] 酸雨 是同一个 trick。俄国人都这么喜欢出接雨水题吗。

考虑位置 i 上方会有多少水，令 l_i=\max\limits_{j=1}^i a_i 且 r_i=\max\limits_{j=i}^n a_i。显然为 \min\left\{l_i,r_i\right\}-a_i。\max 的 \min 不好维护，直接给它拆成 l_i+r_i-\max\{l_i,r_i\}，后者就是全局 \max。于是难点变为维护前缀 \max 的和以及后缀 \max 的和。

以前缀为例，讨论区间 [l,r] 进行 +1 操作对前缀 \max 的影响。观察到如果有影响，那么必然存在一个区间 [l',r'](l\le l'\le r\land r\le r'\le n)；原操作的影响相当于将 [l',r'] 内的所有数 +1。证明显然。这个 [l',r'] 可以用线段树二分找，时间复杂度 O(n\log n)；当然我懒得写于是就写了暴力二分，时间复杂度 O(n\log^2 n)。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
class segtree_max{
  private:
    int k,m;
    vector<int> S,T;
    inline void pushup(int u){
      S[u]=max(S[u<<1],S[u<<1|1]);
    }
    inline void apply(int u,int d){
      S[u]+=d,T[u]+=d;
    }
    inline void pushdown(int u){
      if(T[u]){
        S[u<<1]+=T[u],S[u<<1|1]+=T[u];
        T[u<<1]+=T[u],T[u<<1|1]+=T[u],T[u]=0;
      }
    }
  public:
    segtree_max(vector<int> a){
      int n=a.size();
      k=__lg(n)+(__builtin_popcount(n)>1);
      S.resize((m=1<<k)<<1),T.resize(m<<1);
      for(int i=0;i<n;i++)
        S[i+m]=a[i];
      for(int i=m-1;i;i--)
        pushup(i);
    }
    inline void update(int l,int r,int d=1){
      l+=m,r+=m+1;
      for(int i=k;i;i--){
        if((l>>i<<i)!=l)pushdown(l>>i);
        if((r>>i<<i)!=r)pushdown(r-1>>i);
      }
      int l2=l,r2=r;
      while(l2<r2){
        if(l2&1)apply(l2++,d);
        if(r2&1)apply(--r2,d);
        l2>>=1,r2>>=1;
      }
      for(int i=1;i<=k;i++){
        if((l>>i<<i)!=l)pushup(l>>i);
        if((r>>i<<i)!=r)pushup(r-1>>i);
      }
    }
    inline int prod(int l,int r){
      l+=m,r+=m+1;
      for(int i=k;i;i--){
        if((l>>i<<i)!=l)pushdown(l>>i);
        if((r>>i<<i)!=r)pushdown(r-1>>i);
      }
      int c=0;
      while(l<r){
        if(l&1)c=max(c,S[l++]);
        if(r&1)c=max(c,S[--r]);
        l>>=1,r>>=1;
      }
      return c;
    }
}; // 维护区间加、区间 max 的线段树
class segtree_sum{
  private:
    int k,m;
    vector<pair<ll,int> > S;
    vector<ll> T;
    inline void pushup(int u){
      S[u].first=S[u<<1].first+S[u<<1|1].first;
      S[u].second=S[u<<1].second+S[u<<1|1].second;
    }
    inline void apply(int u,int d){
      S[u].first+=(ll)d*S[u].second,T[u]+=d;
    }
    inline void pushdown(int u){
      if(T[u]){
        S[u<<1].first+=T[u]*S[u<<1].second;
        S[u<<1|1].first+=T[u]*S[u<<1|1].second;
        T[u<<1]+=T[u],T[u<<1|1]+=T[u],T[u]=0;
      }
    }
  public:
    segtree_sum(vector<int> a){
      int n=a.size();
      k=__lg(n)+(__builtin_popcount(n)>1);
      S.resize((m=1<<k)<<1),T.resize(m<<1);
      for(int i=0;i<n;i++)
        S[i+m]=make_pair(a[i],1);
      for(int i=m-1;i;i--)
        pushup(i);
    }
    inline int get(int p){
      p+=m;
      for(int i=k;i;i--)
        pushdown(p>>i);
      return S[p].first;
    }
    inline void update(int l,int r,int d=1){
      l+=m,r+=m+1;
      for(int i=k;i;i--){
        if((l>>i<<i)!=l)pushdown(l>>i);
        if((r>>i<<i)!=r)pushdown(r-1>>i);
      }
      int l2=l,r2=r;
      while(l2<r2){
        if(l2&1)apply(l2++,d);
        if(r2&1)apply(--r2,d);
        l2>>=1,r2>>=1;
      }
      for(int i=1;i<=k;i++){
        if((l>>i<<i)!=l)pushup(l>>i);
        if((r>>i<<i)!=r)pushup(r-1>>i);
      }
    }
    inline ll all_prod(){return S[1].first;}
}; // 维护区间加、区间和的线段树
main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,q,mx=0; ll s=0; cin>>n>>q;
  vector<int> a(n);
  for(auto &i:a)cin>>i,s+=i,mx=max(mx,i);
  vector<int> pr(n),sf(n);
  for(int i=0;i<n;i++)
    pr[i]=max(i?pr[i-1]:0,a[i]);
  for(int i=n-1;~i;i--)
    sf[i]=max(i<n-1?sf[i+1]:0,a[i]);
  segtree_max t(a);
  segtree_sum tp(pr),ts(sf);
  cout<<tp.all_prod()+ts.all_prod()-(ll)mx*n-s<<'\n';
  while(q--){
    int l,r; cin>>l>>r,l--,r--;
    int m=t.prod(l,r);
    mx=max(mx,m+1),s+=r-l+1;
    {
      int L=-1,R=-1;
      int x=l,y=r+1;
      while(x<y){
        int md=x+y>>1;
        if(md==r+1||tp.get(md)==t.prod(l,md))y=md;
        else x=md+1;
      }
      if(y<=r){
        L=y,x=r,y=n-1;
        while(x<y){
          int md=x+y+1>>1;
          if(tp.get(md)==m)x=md;
          else y=md-1;
        }
        R=x,tp.update(L,R);
      }
    } // 更新前缀
    {
      int L=-1,R=-1;
      int x=l-1,y=r;
      while(x<y){
        int md=x+y+1>>1;
        if(md==l-1||ts.get(md)==t.prod(md,r))x=md;
        else y=md-1;
      }
      if(y>=l){
        R=x,x=0,y=l;
        while(x<y){
          int md=x+y>>1;
          if(ts.get(md)==m)y=md;
          else x=md+1;
        }
        L=y,ts.update(L,R);
      }
    } // 更新后缀
    t.update(l,r);
    cout<<tp.all_prod()+ts.all_prod()-(ll)mx*n-s<<'\n';
  }
  return 0;
}