P9485题解

EdenSky · 2023-07-30 22:59:09 · 题解

P9485 积水

• 或许更好的阅读体验

写在前面：这是蒟蒻交的第一篇绿题题解（大祭），因为线性做法比较难想，本篇会着重讲述用 RMQ 问题求解，并尽可能用清晰明了的图片和简易的文字讲明白。

正文

最坏时间复杂度：\mathcal{O}(\sum n+\log \sum n)

在求解之前，先让我们想个问题，如何求解积水格数？再简单点，对于每个 i，其积水高度是多少？看下图。

以 i=3 为例，我们可以发现，每个 i 的积水高度与它的左右两峰有关，左边锋（i=1）高度为 3，是 [1,3) 区间内的最高高度，右边锋（i=5）高度为 4，是 (3,5] 区间内的最高高度。

大家应该都听过木桶效应吧，i=3 时积水最多积 2 格，因为再多就会从 i=1 的位置流出去，所以，积水高度应该是 i 左右两峰的最小值。

那么，上述问题“对于每个 i，求其积水高度”已经转化为“对于每个 i，求其左右峰的高度”，再转化一下：对于每个 i，求 [1,i) 和 (i,n] 两个区间的最大值。

显然这是可以用 DP 求解的，设 l_i 为 i 左边的峰的位置，r_i 为 i 右边的峰的位置，a_i 为 i 的高度。有如下代码：

l[0]=0,l[1]=0;//求l
for(register int i=2;i<=n;i++)
  if(a[i-1]>=a[l[i-1]]) l[i]=i-1;
  else l[i]=l[i-1];

r[n+1]=0,r[n]=0;//求r
for(register int i=n-1;i>=1;i--)
  if(a[i+1]>=a[r[i+1]]) r[i]=i+1;
  else r[i]=r[i+1];

知道了左右两峰的高度，自然而然也就可以求每个 i 的积水格数。代码见下，其中 p_i 为 i 左右两峰的最小值（也可以理解为 i 积水最高可达的高度），w_i 为 i 的积水格数，s 为总积水格数。注意特判 i 自己本身就是峰的情况。

s=0;
for(register int i=1;i<=n;i++){
  p[i]=min(a[l[i]],a[r[i]]);
  if(p[i]-a[i]>0) w[i]=p[i]-a[i];//如果a[i]与左右两峰形成“凹”状
  else w[i]=0;//否则不积水
  s+=w[i];
}

请记住上面的变量符号，后面会用到。

好了，关于积水的问题求解完了，接下来就进入重点了。对于每个 i，有两种情况：

第一类，i 存在积水，即 p_i>a_i。我们对于每个 i，将 a_i 增大至 p_i，即将 i 升高至积水高度，不能多也不能少，多了可能会形成新的峰，增加积水格数，少了无法排尽 i 的积水，看下面的图。

此时将 a_3 提高 2 格，这是恰当好处的，多了的话 i=4 的积水格数会增加，少了也不最优。

因此，有代码（ans 是改造后的答案）：

for(register int i=1;i<=n;i++)
  ans=min(ans,s-w[i]);

第二类，i 是峰。可以尝试降低高度，排出峰内部的积水。这种情况十分复杂，我们要细细研究。

如果我们分别枚举每个 i 降低高度，再加上判断可以减少多少格积水，时间复杂度就会变成惊人的 \mathcal{O}(\sum n_j^2)，这是不可接受的，我们要换种思路。（实际上这种思路的时间复杂度没那么夸张，如果数据水还是能过的）

设 v_i 为将 i 降低后可以减少的积水格数。枚举每个 i，分别求其左右峰（l_i 和 r_i）降低高度后 i 可以减少的积水格数，分别将求出的值加在 v_{l_i} 和 v_{r_i} 即可。

那么如何求可以减少的积水格数呢？

以 i=4 为例，此时 r_i=5。如果将 a_5 降至 0 高度，此时反而会积水（因为此时 a_7 > a_5，形成“凹”状），所以我们只能将 a_5 降至 a_7 的高度，否则会形成多余的积水，那么 i=4 就可以减少 p_4-a_{r_{r_4}}。来解释一下，r_4 是 i=4 的右峰位置，此时我们要将 a_{r_4} 降低，但不能低于 r_4 右边较低峰的位置（图中是 i=7），即不能低于 r_{r_4} 的高度，因此 a_{r_4} 的高度会降至 a_{r_{r_4}}，所以 i=4 可以减少 p_4-a_{r_{r_4}} 格积水。

综上：对于每个 i，使得 v_{r_i}\leftarrow v_{r_i}+(p_i-a_{r_{r_i}})。

那么，如果我们这样写，就可以愉快的 WA 了。

来，看看 i=2 的情况，若按上述想法应减少 2 格积水，但实际上是 1 格，WHY？看看 i=3，当 a_5 降至 a_7 后，它成了 i=2 的右峰，挡住了 i=2 的一部分积水，使得其只能减少 1 格。所以还要求 (i,r_i) 区间内的最大值 y，计算会不会出现新的峰。

这里就是 RMQ 问题了，因为是离线的，可以用 ST 表解决（当然你想用线段树也没人拦你，只是蒟蒻不太会QWQ）。

把上述结论的 a_{r_{r_i}} 改为 \max(a_{r_{r_i}},y) 就好了。

但是！！！还没结束！！！看 i=3，a_5 降至 a_7 后，在区间 [3,7] 中 a_3 是最大的，也就是说 i=3 减少的积水格数是 p_3-a_3，不与 j 或 a_{r_{r_i}} 有关。

所以还要在 \max 内加上第三项 a_i。

这里只讨论了降低右峰的情况，左峰同理。

好啦，上这部分的 Code！

for(register int i=1;i<=n;i++){
  if(p[i]>=a[i]){
  //如果i是峰，不管如何降低a[l[i]]或a[r[i]]都无法增加排水格数
    to=max(a[l[l[i]]],query(l[i]+1,i-1));
    v[l[i]]+=(p[i]-max(to,a[i])>0?
      p[i]-max(to,a[i]):0);//讨论左峰

    to=max(a[r[r[i]]],query(i+1,r[i]-1));
    v[r[i]]+=(p[i]-max(to,a[i])>0?
      p[i]-max(to,a[i]):0);//讨论右峰
  }
}

因此，ans 就可以这样求：

for(register int i=1;i<=n;i++)
  ans=min(ans,s-v[i]);

两类情况讨论完毕，上总 Code！

#define by_wanguan
#include<iostream>
#include<cstring>
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=1e6+7;
ll l[N],r[N],a[N],T,n,v[N],p[N],w[N],s,ans,to;
ll read(){ll x=0,w=1;char ch=0;while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+(ch-'0');ch=getchar();}return x*w;}
void write(ll x){int sta[24],top=0;if(x<0){putchar('-');x=-x;}do{sta[top++]=x%10;x/=10;}while(x);while(top)putchar(sta[--top]+'0');}

/*
l[i] i左边最高位置   r[i] i右边最高位置 
a[i] i高度   p[i] i积水高度 
v[i] i两侧峰削去可减少积水格数
w[i] i积水格数 
*/

//ST表，不会去P3865
  ll lg2[N],pp[22],ma[N][21],len,lg,pl;
  inline void init(){
    pp[0]=1;
    for(register int i=1;i<=20;i++) pp[i]=pp[i-1]*2;
    int cnt=0,last=2;
    for(register int i=2;i<N;i++){
      if(i==last) cnt++,last*=2;
      lg2[i]=cnt;
    }
  }
  inline void solve(){
    for(register int i=1;i<=lg2[n]+1;i++)
      for(register int j=1;j<=n;j++)
        ma[j][i]=max(ma[j][i-1],ma[min(j+pp[i-1],n)][i-1]);
  }
  inline int query(int l,int r){
    if(l>r) return 0;
    if(l==0) l=1;
    len=r-l+1,lg=lg2[len],pl=pp[lg];
    return max(ma[l][lg],ma[r-pl+1][lg]);
  }

signed main(){
  T=read();
  init();
  while(T--){
    n=read();
    for(register int i=1;i<=n;i++)
      a[i]=read(),ma[i][0]=a[i];
    solve();
    l[0]=0,l[1]=0;
    for(register int i=2;i<=n;i++)
      if(a[i-1]>=a[l[i-1]]) l[i]=i-1;
      else l[i]=l[i-1];
    r[n+1]=0,r[n]=0;
    for(register int i=n-1;i>=1;i--)
      if(a[i+1]>=a[r[i+1]]) r[i]=i+1;
      else r[i]=r[i+1];
    s=0;
    for(register int i=1;i<=n;i++){
      p[i]=min(a[l[i]],a[r[i]]);
      if(p[i]-a[i]>0) w[i]=p[i]-a[i];
      else w[i]=0;
      s+=w[i];
    }
    for(int i=1;i<=n;i++) v[i]=0;
    for(register int i=1;i<=n;i++){
      if(p[i]>=a[i]){
        to=max(a[l[l[i]]],query(l[i]+1,i-1));
        v[l[i]]+=(p[i]-max(to,a[i])>0?
          p[i]-max(to,a[i]):0);
        to=max(a[r[r[i]]],query(i+1,r[i]-1));
        v[r[i]]+=(p[i]-max(to,a[i])>0?
          p[i]-max(to,a[i]):0);
      }
    }
    ans=s;
    for(register int i=1;i<=n;i++)
      ans=min(ans,s-w[i]),
      ans=min(ans,s-v[i]);
    write(ans),putchar('\n');
  }
}//Copy不是好习惯哦

AC 记录。

由于 \mathcal{O}(\sum n+\log \sum n) 的复杂度通过 \sum n=10^6 数据较为危险，记得卡常。

还有，如果你只 T 了 Subtask#1 而其它 Subtask 全部 AC，极有可能是 memset() 的问题（别问我怎么知道的）。

还有蒟蒻写了这么多能不能给个赞~~