题解：P14301 [JOI2023 预选赛 R2] 日本沉没 2 / Japan Sinks 2

huizhuyan · 2026-11-11 18:49:20 · 题解

P14301 [JOI2023 预选赛 R2] 日本沉没 2 / Japan Sinks 2

题目简述

给定长度为 N 的海拔数组，有 Q 次操作：

西风 x：在区间 [1,x] 内，所有前缀极大点（左边没有更高的数）海拔 -1。
东风 x：在最右侧 x 个位置，所有后缀极大点（右边没有更高的数）海拔 -1。
查询：输出指定位置当前海拔。

解题思路

核心性质

西风只会作用在 [1,x] 内的前缀极大点，东风只会作用在 [N-x+1,N] 内的后缀极大点。

本题最重要的结论：前缀极大点、后缀极大点的位置不会随着海拔减少而改变。因此，极大点的位置是固定不变的。

我们预处理数组 h_i：

h_i=\min\left(\max_{1\le j\le i}a_j,\max_{i\le j\le N}a_j\right)

表示位置 i 最多能被削减到的海拔上限。

经过若干次操作后，位置 i 的真实海拔为：

\min(h_i,a_i)

线段树维护信息

线段树需要实现以下几个功能：

up：上传子节点信息，更新区间 mx,mn。
build：初始化建树。
add：区间打懒标记。
down：懒标记下传。
peak：查找区间最大值的下标。left=true 取最左最大值，left=false 取最右最大值。
find：在指定区间，按方向查找第一个满足 mn\le 0 的位置。
remove：区间整体减 1，模拟一次风暴削减。
query：单点查询，返回 \min(mx,a_pos)，即当前位置的真实海拔。

操作

西风（op=1）：找到全局最右极大点 r。若 r>x，则在区间 [x+1,r] 中找到第一个触达上限的位置，并将 r 修正为该位置的前一个位置。最后对区间 [1,r] 整体减 1。
东风（op=2）：将 x 转换为 N-x+1，找到全局最左极大点 l。若 x>l，则在区间 [l,x-1] 中查找位置，并将 l 修正为该位置的后一个位置。最后对区间 [l,N] 整体减 1。
查询（op=3）：单点查询，输出当前位置的真实海拔。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF=0x3f3f3f3f3f3f3f3f;
const int N=3e5+10;

int n,q;
int h[N],a[N];
int mx[N<<2],mn[N<<2];
int lazy[N<<2];

void up(int i) {
    mx[i]=max(mx[i<<1],mx[i<<1|1]);
    mn[i]=min(mn[i<<1],mn[i<<1|1]);
}

void build(int l,int r,int i) {
    if(l==r) {
        mx[i]=h[l];
        mn[i]=h[l]-a[l];
        return;
    }
    int mid=(l+r)>>1;
    build(l,mid,i<<1);
    build(mid+1,r,i<<1|1);
    up(i);
}

void add(int i,int v) {
    mx[i]+=v;
    mn[i]+=v;
    lazy[i]+=v;
}

void down(int i) {
    if(lazy[i]) {
        add(i<<1,lazy[i]);
        add(i<<1|1,lazy[i]);
        lazy[i]=0;
    }
}

int peak(int l,int r,int i,bool left) {
    if(l==r) return l;
    int mid=(l+r)>>1;
    down(i);
    if(mx[i<<1]>mx[i<<1|1]||(left&&mx[i<<1]==mx[i<<1|1]))
        return peak(l,mid,i<<1,left);
    return peak(mid+1,r,i<<1|1,left);
}

int find(int jobl,int jobr,int l,int r,int i,int left) {
    if(r<jobl||l>jobr||mn[i]>0) return 0;
    if(l==r) return l;
    int mid=(l+r)>>1;
    down(i);
    if(left) {
        int ans=find(jobl,jobr,l,mid,i<<1,left);
        return ans?ans:find(jobl,jobr,mid+1,r,i<<1|1,left);
    }
    int ans=find(jobl,jobr,mid+1,r,i<<1|1,left);
    return ans?ans:find(jobl,jobr,l,mid,i<<1,left);
}

void remove(int jobl,int jobr,int l,int r,int i) {
    if(jobl<=l&&r<=jobr) {
        add(i,-1);
        return;
    }
    int mid=(l+r)>>1;
    down(i);
    if(jobl<=mid) remove(jobl,jobr,l,mid,i<<1);
    if(mid<jobr) remove(jobl,jobr,mid+1,r,i<<1|1);
    up(i);
}

int query(int jobl,int l,int r,int i) {
    if(l==r) return min(mx[i],a[l]);
    int mid=(l+r)>>1;
    down(i);
    if(jobl<=mid) return query(jobl,l,mid,i<<1);
    else return query(jobl,mid+1,r,i<<1|1);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n>>q;
    for(int i=1;i<=n;++i) {
        cin>>a[i];
        h[i]=max(h[i-1],a[i]);
    }
    for(int i=n,las=0;i;--i) {
        las=max(las,a[i]);
        h[i]=min(h[i],las);
    }
    build(1,n,1);
    for(int i=1,op,x;i<=q;++i) {
        cin>>op>>x;
        if(op==1) {
            int r=peak(1,n,1,0);
            if(x<r) r=find(x+1,r,1,n,1,1)-1;
            remove(1,r,1,n,1);
        }
        else if(op==2) {
            x=n-x+1;
            int l=peak(1,n,1,1);
            if(x>l) l=find(l,x-1,1,n,1,0)+1;
            remove(l,n,1,n,1);
        }
        else cout<<query(x,1,n,1)<<"\n";
    }
    return 0;
}