P11699 [ROIR 2025] 酸雨 Solution

Ptzyc · 2026-07-20 16:53:57 · 题解

模拟赛遇到的，共计 7k 的友好题目。

题解

将题目转化一下：每次给定你一个区间，定义 l_i 为 \max \{ h_l,h_{l + 1} \dots h_i \}，定义 r_i 为 \max \{ h_i,h_{i + 1} \dots h_r \} 对于区间的每个值 d_i 的定义为 \min (l_i,r_i) - h_i，求 \sum d_i。

对于区间的处理，考虑用线段树解决。

具体的，考虑在每次输入后，通过线段树二分处理出所合并的区间，对于区间之后的值全部减一即可。

但原题支持 O(n\log^2 n)，考虑二分 + 线段树即可。

考虑到 - h_i 的过程可以直接用前缀和处理，这里直接处理 \min (l_i,r_i)。

发现对于一个区间 [l,r] 一定存在一个点 p 使得 [l,p - 1] 中 l_i < r_i，[p + 1,r] 中 l_i > r_i。

思考后发现 p 正是区间最大值所在的点。

对于寻找这个点，依旧线段树解决即可。

考虑如何处理出 [l,p - 1] 之间的 \sum l_i，发现如果给定了 p 点就是一个前缀和问题。

考虑把 p - 1 离线下来，通过枚举 p 来依次处理。

考虑单个 p 如何处理，发现似乎通过单调栈维护上一个 \ge h_i 的位置，再拿一颗线段树维护区间赋值以及区间查询即可。

对于 [p + 1,r] 的区间也是同理，倒过来操作即可。

对于以上的三颗线段树都可以融成一颗（避免 MLE）。

总体复杂度 O(n \log^2 n)，如果求区间时用线段树二分可以做到 O(n \log n)。

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <cstring>
#ifdef _WIN32
#define getchar _getchar_nolock
#define putchar _putchar_nolock
#else
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define pll pair<ll,ll>
#define pld pair<ld,ld>
typedef long long ll;
typedef long double ld;
typedef __int128 i128;
namespace io {
    using namespace std;
    template <typename T> void debug (T x) {
        cerr<<x<<'\n';
    }
    template <typename T> void debuglen (T x) {
        cerr<<x<<' ';
    }
    template <typename T,typename...Args> void debug (T x,Args...args) {
        cerr<<x<<' ';
        debug(args...);
    }
    template <typename T> void debug (T *lt,T *rt) {
        ll len=rt-lt;
        for (ll i=0;i<len;i++) {
            debuglen(*(lt+i));
        }
        cerr<<'\n';
    }
    inline ll read () {
        char x=getchar();
        ll ans=0,f=1;
        while (x<'0'||x>'9') {
            if (x=='-') {
                f=-1;
            }
            x=getchar();
        }
        while (x>='0'&&x<='9') {
            ans=(ans<<1)+(ans<<3);
            ans+=(x^'0');
            x=getchar();
        }
        return ans*f;
    }
    void print (ll x) {
        if (x<0) {
            x=-x;
            putchar('-');
        }
        if (x>=10) {
            print(x/10);
        }
        putchar(x%10+'0');
    }
}
using namespace io;
const ll N=1e5+5,mod=1e9+7,inf=2e18;
const ld eps=1e-6;
struct node {
    ll l,r;
} q[N];
ll n,a[N],ans[N],sum[N];
ll st[N],top;
vector<pll> vl[N],vr[N];
struct Segtree {
    ll t[N<<2],lt[N<<2];
    inline void push_up (ll pos) {
        t[pos]=t[pos<<1]+t[pos<<1|1];
    }
    inline void push_down (ll pos) {
        if (!lt[pos]) {
            return ;
        }
        t[pos<<1]+=lt[pos];
        t[pos<<1|1]+=lt[pos];
        lt[pos<<1]+=lt[pos];
        lt[pos<<1|1]+=lt[pos];
        lt[pos]=0;
    }
    void build (ll pos,ll l,ll r) {
        if (l==r) {
            t[pos]=l;
            return ;
        }
        ll mid=(l+r)>>1;
        build(pos<<1,l,mid);
        build(pos<<1|1,mid+1,r);
        push_up(pos);
    }
    inline void push_upl (ll pos) {
        t[pos]=t[pos<<1];
        if (a[t[pos<<1|1]]>a[t[pos]]) {
            t[pos]=t[pos<<1|1];
        }
    }
    void rebuild (ll pos,ll l,ll r) {
        if (l==r) {
            t[pos]=l;
            return ;
        }
        ll mid=(l+r)>>1;
        rebuild(pos<<1,l,mid);
        rebuild(pos<<1|1,mid+1,r);
        push_upl(pos);
    }
    void rerebuild (ll pos,ll l,ll r) {
        lt[pos]=0;
        if (l==r) {
            t[pos]=0;
            return ;
        }
        ll mid=(l+r)>>1;
        rerebuild(pos<<1,l,mid);
        rerebuild(pos<<1|1,mid+1,r);
        push_up(pos);
    }
    ll ask (ll pos,ll l,ll r,ll L,ll R) {
        if (L<=l&&r<=R) {
            return t[pos];
        }
        ll mid=(l+r)>>1,cnt=0;
        if (L<=mid) {
            cnt=ask(pos<<1,l,mid,L,R);
        }
        if (R>mid) {
            ll kl=ask(pos<<1|1,mid+1,r,L,R);
            if (!cnt||a[cnt]<a[kl]) {
                cnt=kl;
            }
        }
        return cnt;
    }
    void add (ll pos,ll l,ll r,ll L,ll R) {
        if (L<=l&&r<=R) {
            t[pos]--;
            lt[pos]--;
            return ;
        }
        ll mid=(l+r)>>1;
        push_down(pos);
        if (L<=mid) {
            add(pos<<1,l,mid,L,R);
        }
        if (R>mid) {
            add(pos<<1|1,mid+1,r,L,R);
        }
        push_up(pos);
    }
    ll query (ll pos,ll l,ll r,ll x) {
        if (l==r) {
            return t[pos];
        }
        ll mid=(l+r)>>1;
        push_down(pos);
        if (x<=mid) {
            return query(pos<<1,l,mid,x);
        }
        return query(pos<<1|1,mid+1,r,x);
    }
    inline void push_downl (ll pos,ll l,ll r) {
        ll mid=(l+r)>>1;
        if (!lt[pos]) {
            return ;
        }
        t[pos<<1]=lt[pos]*(mid-l+1);
        t[pos<<1|1]=lt[pos]*(r-mid);
        lt[pos<<1]=lt[pos<<1|1]=lt[pos];
        lt[pos]=0;
    }
    void cover (ll pos,ll l,ll r,ll L,ll R,ll x) {
        if (L<=l&&r<=R) {
            lt[pos]=x;
            t[pos]=x*(r-l+1);
            return ;
        }
        ll mid=(l+r)>>1;
        push_downl(pos,l,r);
        if (L<=mid) {
            cover(pos<<1,l,mid,L,R,x);
        }
        if (R>mid) {
            cover(pos<<1|1,mid+1,r,L,R,x);
        }
        push_up(pos);
    }
    ll find (ll pos,ll l,ll r,ll L,ll R) {
        if (L<=l&&r<=R) {
            return t[pos];
        }
        ll mid=(l+r)>>1,cnt=0;
        push_downl(pos,l,r);
        if (L<=mid) {
            cnt=find(pos<<1,l,mid,L,R);
        }
        if (R>mid) {
            cnt+=find(pos<<1|1,mid+1,r,L,R);
        }
        return cnt;
    }
} tr;
inline ll get_l (ll x) {
    ll l=1,r=n,cnt=0;
    while (l<=r) {
        ll mid=(l+r)>>1;
        if (tr.query(1,1,n,mid)>=x) {
            cnt=mid;
            r=mid-1;
        }
        else {
            l=mid+1;
        }
    }
    return cnt;
}
inline ll get_r (ll x) {
    ll l=1,r=n,cnt=0;
    while (l<=r) {
        ll mid=(l+r)>>1;
        if (tr.query(1,1,n,mid)<=x) {
            cnt=mid;
            l=mid+1;
        }
        else {
            r=mid-1;
        }
    }
    return cnt;
}
inline void solve () {
    n=read();
    for (ll i=1;i<=n;i++) {
        a[i]=read();
        sum[i]=sum[i-1]+a[i];
    }
    tr.build(1,1,n);
    for (ll i=1;i<n;i++) {
        ll x=read();
        q[i]={get_l(x),get_r(x+1)};
        tr.add(1,1,n,get_r(x)+1,n);
    }
    tr.rebuild(1,1,n);
    for (ll i=1;i<n;i++) {
        ll l=q[i].l,r=q[i].r,pos=0;
        pos=tr.ask(1,1,n,l,r);
        vl[l].push_back({i,pos});
        vr[r].push_back({i,pos});
        ans[i]=-a[pos]-sum[r]+sum[l-1];
    }
    tr.rerebuild(1,1,n);
    top=0;
    for (ll i=1;i<=n;i++) {
        while (top&&a[st[top]]<a[i]) {
            top--;
        }
        tr.cover(1,1,n,st[top]+1,i,a[i]);
        for (auto it : vr[i]) {
            ans[it.first]+=tr.find(1,1,n,it.second,i);
        }
        st[++top]=i;
    }
    tr.rerebuild(1,1,n);
    top=0;
    st[0]=n+1;
    for (ll i=n;i;i--) {
        while (top&&a[st[top]]<a[i]) {
            top--;
        }
        tr.cover(1,1,n,i,st[top]-1,a[i]);
        for (auto it : vl[i]) {
            ans[it.first]+=tr.find(1,1,n,i,it.second);
        }
        st[++top]=i;
    }
    for (ll i=1;i<n;i++) {
        print(ans[i]);
        puts("");
    }
}
int main () {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ll T=1;
    // T=read();
    while (T--) {
        solve();
    }
    return 0;
}