题解：AT_joisc2016_h 回転寿司

· · 题解

前言

一道水的黑分块。

思路

观察到这个环可以拆成序列，只要将 l>r 的数据变为 [r,n] 与 [1,l] 即可。我们手模一下可以发现一个性质：对于一个数 x，在区间 [l,r] 中遍历一遍后，最终换出来的数一定是 [l,r] 中最大的数，于是便想到了分块处理。具体来说，对于每个整块，维护一个大根堆，记录这块中最大的数是多少。同时记录下每块中打上的 tag，即新添进去的寿司的价格。而对于散块，我们可以遍历我们记录的 tag，一个个将标记下放后再处理散块。不过这个的时间复杂度为 O(q\sqrt n\log n+qn)，理论上会超时。但是我硬是卡过去了。

于是我们考虑对散块进行优化。由于每次整块进去的顺序都有先后，可以发现一个优化：我们将 tag 也按小根堆记录，然后遍历这个整块，每次令 a_i 为堆顶的数，并将堆顶的 tag 弹出。这样时间复杂度就是 O(q\sqrt n\log n)。

:::success[code]

#include<bits/stdc++.h>
using namespace std;
static int n,m,a[400005],t,l[1005],r[1005],p[400005],siz;
static priority_queue<int>q[1005];
static priority_queue<int,vector<int>,greater<int> >tag[1005];
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<48||ch>57){
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>=48&&ch<=57){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
inline int modify(const int x,const int y,int k){
    if(p[x]==p[y]){
        for(int i=l[p[x]];i<=r[p[y]];++i){
            tag[p[x]].push(a[i]);
            a[i]=tag[p[x]].top();
            tag[p[x]].pop();
        }
        for(int i=l[p[x]];i<=r[p[y]];++i)q[p[x]].pop();
        while(!tag[p[x]].empty())tag[p[x]].pop();
        for(int i=x;i<=y;++i){
            if(a[i]>k){
                a[i]^=k^=a[i]^=k;
            }
        }
        q[p[x]]=priority_queue<int>(a+l[p[x]],a+r[p[y]]+1);
    }
    else{
        for(int i=l[p[x]];i<=r[p[x]];++i){
            tag[p[x]].push(a[i]);
            a[i]=tag[p[x]].top();
            tag[p[x]].pop();
        }
        for(int i=l[p[x]];i<=r[p[x]];++i)q[p[x]].pop();
        while(!tag[p[x]].empty())tag[p[x]].pop();
        for(int i=x;i<=r[p[x]];++i){
            if(a[i]>k){
                a[i]^=k^=a[i]^=k;
            }
        }
        q[p[x]]=priority_queue<int>(a+l[p[x]],a+r[p[x]]+1);
        for(int i=p[x]+1;i<=p[y]-1;++i){
            if(q[i].top()>k){
                int v=q[i].top();
                q[i].pop();
                q[i].push(k);
                tag[i].push(k);
                k=v;
            }
        }
        for(int i=l[p[y]];i<=r[p[y]];++i){
            tag[p[y]].push(a[i]);
            a[i]=tag[p[y]].top();
            tag[p[y]].pop();
        }
        for(int i=l[p[y]];i<=r[p[y]];++i)q[p[y]].pop();
        while(!tag[p[y]].empty())tag[p[y]].pop();
        for(int i=l[p[y]];i<=y;++i){
            if(a[i]>k){
                a[i]^=k^=a[i]^=k;
            }
        }
        q[p[y]]=priority_queue<int>(a+l[p[y]],a+r[p[y]]+1);
    }
    return k;
}
signed main(){
//  freopen("P14400_1.in","r",stdin);
//  freopen("P14400.out","w",stdout);
    n=read(),m=read();
    for(int i=1;i<=n;++i)a[i]=read();
    t=sqrt(n)*0.6;
    siz=n/t;
    for(int i=1;i<=t;++i){
        l[i]=(i-1)*siz+1;
        r[i]=i*siz;
    }
    if(r[t]!=n){
        t++;
        l[t]=r[t-1]+1;
        r[t]=n;
    }
    for(int i=1;i<=t;++i){
        for(int j=l[i];j<=r[i];++j){
            p[j]=i;
            q[i].push(a[j]);
        }
    }
    while(m--){
        int x,y,k;
        x=read(),y=read(),k=read();
        if(x<=y){
            cout<<modify(x,y,k)<<'\n';
        }
        else{
            int v=modify(x,n,k);
            cout<<modify(1,y,v)<<'\n';
        }
    }
    return 0;
}

::::