P14400 [JOISC 2016] 回转寿司 / Sushi

题意简介

给定一个长度为 \(n\) 的环状数组，每次询问给出 \(l,r,x\)，依次遍历 \(i = l , \cdots , r\)（如果 \(l > r\)，从 \(l\) 遍历到 \(n\)，再从 \(1\) 遍历到 \(r\)），若 \(a_i > x\)，则交换二者的值，输出最终 \(x\) 的值，询问之间不互相独立。

思路

每次询问的答案是显然的，\(x = \max \limits_{ i = l } ^ r a_i\)，对于 \(a\) 数组的改变，如果每次暴力修改，时间复杂度 \(\mathcal{ O ( n q ) }\)，不可接受。数据范围 \(N_{max} = 4 \times 10^5\)，考虑分块，对每个块维护一个大根堆，那么块内每次更新后有哪些元素很好维护，只需将堆顶与 \(x\) 交换即可，关键在于如何对应每个元素所在的位置。

在对同一个块询问的所有 \(x\) 里取最小的一个记为 \(t\)，若 \(a_i < x\)，则用 \(a_i\) 替换 \(x\)，于是我们可以对每个块维护一个小根堆，记录对这个块的所有操作，遍历块中元素对应更新即可。

时间复杂度 \(\mathcal{ O ( q \sqrt{ n } \log n ) }\)。

Code

#include<iostream>
#include<queue>
#include<cmath>
#include<vector>
#include<utility>
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N=4e5+5;
const int N_SQRT=655;
int n,blo,Q,val[N],bl[N];
priority_queue<int,vector<int>,less<int>>Ele[N_SQRT];
priority_queue<int,vector<int>,greater<int>>Ask[N_SQRT];
void Rebuild(int x)
{if(Ask[x].empty()) return;for(int i=(x-1)*blo+1;i<=min(n,x*blo);i++)if(val[i]>Ask[x].top())Ask[x].push(val[i]),val[i]=Ask[x].top(),Ask[x].pop();while(!Ask[x].empty()) Ask[x].pop();
}
void Insert(int x)
{while(!Ele[x].empty()) Ele[x].pop();for(int i=(x-1)*blo+1;i<=min(n,x*blo);i++)Ele[x].push(val[i]);
}
int Query(int L,int R,int x)
{Rebuild(bl[L]);for(int i=L;i<=min(R,bl[L]*blo);i++)if(x<val[i]) swap(x,val[i]);Insert(bl[L]);for(int i=bl[L]+1;i<=bl[R]-1;i++){if(x>=Ele[i].top()) continue;Ask[i].push(x),Ele[i].push(x);x=Ele[i].top(),Ele[i].pop();}if(bl[L]!=bl[R]){Rebuild(bl[R]);for(int i=(bl[R]-1)*blo+1;i<=R;i++)if(x<val[i]) swap(x,val[i]);Insert(bl[R]);}return x;
}
int main()
{IOS;cin>>n>>Q;blo=sqrt(n);for(int i=1;i<=n;i++)cin>>val[i],bl[i]=(i-1)/blo+1,Ele[bl[i]].push(val[i]);while(Q--){int L,R,x;cin>>L>>R>>x;if(L>R) cout<<Query(1,R,Query(L,n,x))<<'\n';else cout<<Query(L,R,x)<<'\n';}return 0;
}

完结撒花～