题解：P14400 [JOISC 2016] 回转寿司 / Sushi

_O_v_O_ · 2025-11-04 15:08:23 · 题解

神题。。。

首先，我们发现一次询问最后的答案肯定为 [l,r] 的最大值。

那么我们就考虑分块，我们可以为每个块都维护一个大根堆，遇到一个块时，就将当前 A 加入当前块的堆，然后将 A 设为堆内最大值并弹出它。

然后我们就发现这样的操作是维护不了所有数的顺序的，因此只适用于整块。

那么散块呢？

我们发现，在 A 的视角下：我们可以视为 A_j 与较小的 a_i 交换，那么我们就可以同时为每个块再维护一个小根堆代表块内询问的数，每次直接暴力重构堆整个块即可。

我们注意到这样单次操作复杂度是 O(\frac{n}{B}\log n+B\log n)，取 B 为 \sqrt{n} 时平衡，总时间复杂度为 O(n\log n+q\sqrt{n}\log n)，看似跑不过，实测时间 9 秒可以跑过。

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=4e5+5,B=666;
int n,m,block,belong[N],L[B],R[B],a[N];
priority_queue<int,vector<int>,less<int>> qp[B];
priority_queue<int,vector<int>,greater<int>> qp2[B];

int bl(int A,int l,int r,int x){
    for(int i=L[A];i<=R[A];i++){
        qp2[A].push(a[i]);
        a[i]=qp2[A].top();
        qp2[A].pop();
    }
    for(int i=l;i<=r;i++) if(a[i]>x) swap(a[i],x);
    while(!qp[A].empty()) qp[A].pop();
    while(!qp2[A].empty()) qp2[A].pop();
    for(int i=L[A];i<=R[A];i++) qp[A].push(a[i]); 
    return x;
}

int query(int l,int r,int x){
    if(belong[l]==belong[r]) return bl(belong[l],l,r,x);
    else{
        x=bl(belong[l],l,R[belong[l]],x);
        for(int i=belong[l]+1;i<=belong[r]-1;i++) qp[i].push(x),qp2[i].push(x),x=qp[i].top(),qp[i].pop();
        return bl(belong[r],L[belong[r]],r,x);
    }
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;block=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        belong[i]=ceil(1.0*i/block);
    }
    for(int i=1;i<=belong[n];i++){
        L[i]=R[i-1]+1,R[i]=i*block;
        for(int j=L[i];j<=R[i];j++) qp[i].push(a[j]);
    }
    R[belong[n]]=n;
    while(m--){
        int l,r,x;
        cin>>l>>r>>x;
        if(l>r) cout<<query(1,r,query(l,n,x))<<endl;
        else cout<<query(l,r,x)<<endl;
    }
    return 0;
}