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

· · 题解

环，直接将 l>r 的询问拆成两个询问做即可。

考虑到一次询问后，若有过交换，x 一定是区间最大值。

说明区间中的最大值被取出，x 被丢进去了。

如果询问都是全局的，可以发现其实我们连 x 被放在哪里都不关心，只需维护一个大根堆就可以做。

考虑分块。类比全局，整块是简单的。但是散块我们需要知道元素的顺序。

直接维护做不到，但我们可以根据之前对这个块的整块修改重构这个块。具体来说，维护修改 x 的小根堆然后从左往右扫每次取最小和当前 a_i 比较做交换。

#include<bits/stdc++.h>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read(){
    register int x=0,s=gc;while(!isdigit(s))s=gc;
    while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
    return x;
}
const int N=400005,blk=600,S=N/blk+5;
int n,m,tot,L[S],R[S];
int a[N],bl[N];
priority_queue<int> q[S],p[S];
inline void push(int id,int &x){
    if(q[id].top()>x){
        int X=q[id].top();
        p[id].push(-x),q[id].pop(),q[id].push(x),x=X;
    }
}
inline void reb(int id){
    if(p[id].size()){
        for(int i=L[id];i<=R[id];++i)
            if(a[i]>-p[id].top()){
                int X=-p[id].top();
                p[id].pop(),p[id].push(-a[i]),a[i]=X;
            }
        while(p[id].size())p[id].pop();
    }
    while(q[id].size())q[id].pop();
    for(int i=L[id];i<=R[id];++i)q[id].push(a[i]);
}
inline void ask(int l,int r,int &x){
    if(bl[l]==bl[r]){
        reb(bl[l]);
        for(int i=l;i<=r;++i)if(a[i]>x)swap(a[i],x);
        return reb(bl[l]);
    }
    ask(l,R[bl[l]],x);
    for(int i=bl[l]+1;i<bl[r];++i)push(i,x);
    ask(L[bl[r]],r,x);
}
signed main()
{
    n=rd,m=rd,tot=(n-1)/blk+1;for(int i=1;i<=n;bl[i]=(i-1)/blk+1,++i)a[i]=rd;
    for(int i=1;i<=tot;++i)L[i]=R[i-1]+1,R[i]=i*blk;R[tot]=n;
    for(int i=1;i<=n;++i)q[bl[i]].push(a[i]);
    for(int i=1,l,r,x;i<=m;++i)l=rd,r=rd,x=rd,
        l>r?ask(l,n,x),ask(1,r,x):ask(l,r,x),cout<<x<<'\n';
    return 0;
}