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

lzx111218 · 2025-11-12 21:29:56 · 题解

P14400 [JOISC 2016] 回转寿司 / Sushi

题目传送门

思路

在一个环形数组中，处理多轮查询。每轮查询给定起点 S、终点 T 和初始值 P，需要让 P 沿环形数组逆时针从 S 移动到 T，途经每个元素时，若元素值大于 P 则交换两者，求最终移动结束后 P 的值。

很明显的分块。

• 将数组划分为块大小 B = \sqrt{N} 的块，共 O(\sqrt{N}) 个块；
• 每个块维护两个堆：
  • 大根堆：存储块内元素，取最大值。
  • 小根堆：辅助重构块内元素。
• 记录每个块的左右边界 L_i、R_i，以及每个位置所属的块 a_i。

处理查询

每轮查询需根据 S 和 T 的位置分两种情况处理：

1. 路径为连续区间 [S, T]，直接处理该区间即可。
2. 路径分为两个连续区间 [S, N] 和 [1, T]，分别处理后合并结果。

块内处理

1. 不完整块：

   • 先通过小根堆重构块内元素；
   • 遍历区间内的每个元素，若元素值大于当前 P 则交换；
   • 交换后重新用大根堆记录块内元素，更新块的状态。

2. 完整块：

   • 将当前 P 加入堆，弹出堆中最大值；
   • 块内元素的最大值被移除，剩余元素仍由堆维护就行。

总时间复杂度为 \mathcal{O}(Q \times \sqrt{N} \log N) \approx 3 \times 10^7。

:::success[代码]

#include<bits/stdc++.h>
using namespace std;
#define int unsigned long long
namespace fastIO{char *p1,*p2,buf[100000];
    #define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
    inline void read(int&n){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=nc();}while(ch>=48&&ch<=57){x=(x<<3)+(x<<1)+(ch^48),ch=nc();}n=x*f;}
    inline void read(string&s){char ch=nc();while(ch==' '||ch=='\n'){ch=nc();}while(ch!=' '&&ch!='\n'){s+=ch,ch=nc();}}
    inline void read(char&ch){ch=nc();while(ch==' '||ch=='\n'){ch=nc();}}
    inline void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}
    inline void write(const string&s){for(register int i=0;i<(int)s.size();i++){putchar(s[i]);}}
    inline void write(const char&c){putchar(c);}
}using namespace fastIO;
constexpr int N = 4e5 + 91, M = 9178;
int n, m, crush, a[N], L[M], R[M], val[N];
priority_queue<int, vector<int>, less<int>> qp[M];
priority_queue<int, vector<int>, greater<int>> qp2[M];
signed main(){
    read(n), read(m); 
    crush = sqrt(n);
    for(int i = 1; i <= n; i++){
        read(val[i]);
        a[i] = ceil(1.0 * i / crush);
    }
    for(int i = 1; i <= a[n]; i++){
        L[i] = R[i - 1] + 1;
        R[i] = i * crush;
        for(int j = L[i]; j <= R[i]; j++){
            qp[i].push(val[j]);
        }
    }
    R[a[n]] = n;
    while(m--){
        int l, r, x;
        read(l), read(r), read(x);
        if(l > r){
            int il = l, ir = n, ix = x;
            int tmp;
            if(a[il] == a[ir]){
                int A = a[il];
                int ll = il, rr = ir;
                int xx = ix;
                for(int i = L[A]; i <= R[A]; i++){
                    qp2[A].push(val[i]);
                    val[i] = qp2[A].top();
                    qp2[A].pop();
                }
                for(int i = ll; i <= rr; i++){
                    if(val[i] > xx) swap(val[i], xx);
                }
                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(val[i]);
                }
                tmp = xx;
            }else{
                int Al = a[il];
                int ll = il, rr = R[Al];
                int xx = ix;
                for(int i = L[Al]; i <= R[Al]; i++){
                    qp2[Al].push(val[i]);
                    val[i] = qp2[Al].top();
                    qp2[Al].pop();
                }
                for(int i = ll; i <= rr; i++){
                    if(val[i] > xx) swap(val[i], xx);
                }
                while(!qp[Al].empty()) qp[Al].pop();
                while(!qp2[Al].empty()) qp2[Al].pop();
                for(int i = L[Al]; i <= R[Al]; i++){
                    qp[Al].push(val[i]);
                }
                int xi = xx;

                for(int i = a[il] + 1; i <= a[ir] - 1; i++){
                    qp[i].push(xi);
                    qp2[i].push(xi);
                    xi = qp[i].top();
                    qp[i].pop();
                }

                int Ar = a[ir];
                int llr = L[Ar], rrr = ir;
                int xxr = xi;
                for(int i = L[Ar]; i <= R[Ar]; i++){
                    qp2[Ar].push(val[i]);
                    val[i] = qp2[Ar].top();
                    qp2[Ar].pop();
                }
                for(int i = llr; i <= rrr; i++){
                    if(val[i] > xxr) swap(val[i], xxr);
                }
                while(!qp[Ar].empty()) qp[Ar].pop();
                while(!qp2[Ar].empty()) qp2[Ar].pop();
                for(int i = L[Ar]; i <= R[Ar]; i++){
                    qp[Ar].push(val[i]);
                }
                tmp = xxr;
            }

            int ol = 1, o_r = r, ox = tmp;
            int res;
            if(a[ol] == a[o_r]){
                int A = a[ol];
                int ll = ol, rr = o_r;
                int xx = ox;
                for(int i = L[A]; i <= R[A]; i++){
                    qp2[A].push(val[i]);
                    val[i] = qp2[A].top();
                    qp2[A].pop();
                }
                for(int i = ll; i <= rr; i++){
                    if(val[i] > xx) swap(val[i], xx);
                }
                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(val[i]);
                }
                res = xx;
            }else{
                int Al = a[ol];
                int ll = ol, rr = R[Al];
                int xx = ox;
                for(int i = L[Al]; i <= R[Al]; i++){
                    qp2[Al].push(val[i]);
                    val[i] = qp2[Al].top();
                    qp2[Al].pop();
                }
                for(int i = ll; i <= rr; i++){
                    if(val[i] > xx) swap(val[i], xx);
                }
                while(!qp[Al].empty()) qp[Al].pop();
                while(!qp2[Al].empty()) qp2[Al].pop();
                for(int i = L[Al]; i <= R[Al]; i++){
                    qp[Al].push(val[i]);
                }
                int xo = xx;

                for(int i = a[ol] + 1; i <= a[o_r] - 1; i++){
                    qp[i].push(xo);
                    qp2[i].push(xo);
                    xo = qp[i].top();
                    qp[i].pop();
                }

                int Ar = a[o_r];
                int llr = L[Ar], rrr = o_r;
                int xxr = xo;
                for(int i = L[Ar]; i <= R[Ar]; i++){
                    qp2[Ar].push(val[i]);
                    val[i] = qp2[Ar].top();
                    qp2[Ar].pop();
                }
                for(int i = llr; i <= rrr; i++){
                    if(val[i] > xxr) swap(val[i], xxr);
                }
                while(!qp[Ar].empty()) qp[Ar].pop();
                while(!qp2[Ar].empty()) qp2[Ar].pop();
                for(int i = L[Ar]; i <= R[Ar]; i++){
                    qp[Ar].push(val[i]);
                }
                res = xxr;
            }
            write(res);
            putchar('\n');
        }else{
            int cl = l, cr = r, cx = x;
            int res;
            if(a[cl] == a[cr]){
                int A = a[cl];
                int ll = cl, rr = cr;
                int xx = cx;
                for(int i = L[A]; i <= R[A]; i++){
                    qp2[A].push(val[i]);
                    val[i] = qp2[A].top();
                    qp2[A].pop();
                }
                for(int i = ll; i <= rr; i++){
                    if(val[i] > xx) swap(val[i], xx);
                }
                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(val[i]);
                }
                res = xx;
            }else{
                int Al = a[cl];
                int ll = cl, rr = R[Al];
                int xx = cx;
                for(int i = L[Al]; i <= R[Al]; i++){
                    qp2[Al].push(val[i]);
                    val[i] = qp2[Al].top();
                    qp2[Al].pop();
                }
                for(int i = ll; i <= rr; i++){
                    if(val[i] > xx) swap(val[i], xx);
                }
                while(!qp[Al].empty()) qp[Al].pop();
                while(!qp2[Al].empty()) qp2[Al].pop();
                for(int i = L[Al]; i <= R[Al]; i++){
                    qp[Al].push(val[i]);
                }
                int xc = xx;

                for(int i = a[cl] + 1; i <= a[cr] - 1; i++){
                    qp[i].push(xc);
                    qp2[i].push(xc);
                    xc = qp[i].top();
                    qp[i].pop();
                }

                int Ar = a[cr];
                int llr = L[Ar], rrr = cr;
                int xxr = xc;
                for(int i = L[Ar]; i <= R[Ar]; i++){
                    qp2[Ar].push(val[i]);
                    val[i] = qp2[Ar].top();
                    qp2[Ar].pop();
                }
                for(int i = llr; i <= rrr; i++){
                    if(val[i] > xxr) swap(val[i], xxr);
                }
                while(!qp[Ar].empty()) qp[Ar].pop();
                while(!qp2[Ar].empty()) qp2[Ar].pop();
                for(int i = L[Ar]; i <= R[Ar]; i++){
                    qp[Ar].push(val[i]);
                }
                res = xxr;
            }
            write(res);
            putchar('\n');
        }
    }
    return 0;
}

:::