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

· · 题解

题意

给定一个长为 n 的环，然后有 q 次操作，每次操作给定一个 x，然后从 l 遍历到 r，若遍历到的元素大于 x，就交换 x 与遍历到的元素，每次操作输出最后的 x。

题解

好可爱的分块题。

首先把环拆开，然后就相当于在区间上进行操作。

不难注意到假设当前区间没有被操作过，那么你最后的 x 一定是这个区间的最大值或一开始给定的 x，然后对于子任务 2 就很简单了：维护一个大根堆，对于每次操作比较堆顶和 x，若 x 大则不管，否则把堆顶取出来输出，把 x 放进去。

可以发现在这个做法中你并不在意每个值具体位于那个位置，我们只知道序列上到底存在那些值。

然后考虑如何把这个做法搬到区间上，可以使用分块。

对于每一个块，维护一个全局做法，然后如果每次询问整块就做完了。

困难的是如何应对散块的部分，我们发现一个区间先插 x 后插 y 与先插 y 后插 x 是完全一样的，都是只有更小的值会被留下。

这提示我们对于每一个块对曾经的修改开一个小根堆，然后对于散块操作从左往右扫一遍，用堆顶与当前值比较。注意到若当前的值被换了还会影响后面的值，所以把当前值（如果被交换了）也插进堆里，然后对块暴力修改并统计答案即可。

对于复杂度，因为散块和整块都有堆，所以 \log 平衡不掉，直接是 \mathcal O(n \sqrt n \log n) 的。

代码

注意，为了避免杂七杂八的分类讨论，可以在堆里插哨兵。

#include<bits/stdc++.h>
/*
据说有七成的高中生情侣会在一年内分手

若连毕业后的也算上，几乎可以说是全军覆没

但所有人依然投身于恋爱的折腾

时而哭泣，时而欢笑

我并不期望现实和自己的内心会被这种短暂的关系动摇

但我有时会想

如果我有那种青春的话

要是眼前会有那种为我流泪的女主角的话

要是我是轻小说男主角的话

那个时候，我会有什么感受呢？
*/
using namespace std;
const int S=600,N=400005;
int n,q,L[N+5],R[N+5],bel[N+5],a[N+5];
priority_queue<int,vector<int>,less<int> >dg[N/S+15];
priority_queue<int,vector<int>,greater<int> >xg[N/S+15];
void rebuild(int b){
    for(int i=L[b];i<=R[b];i++){
        if(a[i]>xg[b].top()){
            int t=a[i];
            a[i]=xg[b].top();
            xg[b].pop();
            xg[b].push(t);
        }
    }
    while(!xg[b].empty())xg[b].pop();
    xg[b].push(1e9);
    while(!dg[b].empty())dg[b].pop();
}
void puush(int b){
    for(int i=L[b];i<=R[b];i++)dg[b].push(a[i]);
}
int update(int l,int r,int x){
    if(bel[l]==bel[r]){
//      puts(":::::");
//      for(int i=L[bel[l]];i<=R[bel[r]];i++)printf("%d ",a[i]);
//      puts("");
        rebuild(bel[l]);
        for(int i=l;i<=r;i++){
            if(a[i]>x)swap(a[i],x);
        }
        puush(bel[l]); 
    }else{
        rebuild(bel[l]);
        for(int i=l;i<=R[bel[l]];i++){
            if(a[i]>x)swap(a[i],x);
        }
        puush(bel[l]); 
        for(int i=bel[l]+1;i<=bel[r]-1;i++){
            if(dg[i].top()>x){
                int t=x;
                x=dg[i].top();
                dg[i].pop();
                dg[i].push(t);
                xg[i].push(t);
            }
        }
        rebuild(bel[r]);
        for(int i=L[bel[r]];i<=r;i++){
            if(a[i]>x)swap(a[i],x);
        }
        puush(bel[r]); 
    }
    return x;
}
signed main(){
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        bel[i]=(i-1)/S+1;
        dg[bel[i]].push(a[i]);
    }
    for(int i=1;i<=bel[n];i++)xg[i].push(1e9); //插一个哨兵 
    for(int i=1;i<=n;i++)R[bel[i]]=i;
    for(int i=n;i>=1;i--)L[bel[i]]=i;
    for(int i=1;i<=q;i++){
        int l,r,x;
        scanf("%d %d %d",&l,&r,&x);
        if(r<l){
            int c=update(l,n,x);
            printf("%d\n",update(1,r,c));
        }else printf("%d\n",update(l,r,x));
    }
}