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

神题。。。

首先，我们发现一次询问最后的答案肯定为

[l,r]

的最大值。

那么我们就考虑分块，我们可以为每个块都维护一个大根堆，遇到一个块时，就将当前

A

加入当前块的堆，然后将

A

设为堆内最大值并弹出它。

然后我们就发现这样的操作是维护不了所有数的顺序的，因此只适用于整块。

那么散块呢？

我们发现，在

A

的视角下：我们可以视为

A_j

与较小的

a_i

交换，那么我们就可以同时为每个块再维护一个小根堆代表块内询问的数，每次直接暴力重构堆整个块即可。

我们注意到这样单次操作复杂度是

O(\frac{n}{B}\log n+B\log n)

，取

B

为

\sqrt{n}

时平衡，总时间复杂度为

O(n\log n+q\sqrt{n}\log n)

，看似跑不过，实测时间

9

秒可以跑过。

代码：

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int N=4e5+5,B=666;
int n,m,block,belong[N],L[B],R[B],a[N];
priority_queue<int,vector<int>,less<int>> qp[B];
priority_queue<int,vector<int>,greater<int>> qp2[B];

int bl(int A,int l,int r,int x){
	for(int i=L[A];i<=R[A];i++){
		qp2[A].push(a[i]);
		a[i]=qp2[A].top();
		qp2[A].pop();
	}
	for(int i=l;i<=r;i++) if(a[i]>x) swap(a[i],x);
	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(a[i]); 
	return x;
}

int query(int l,int r,int x){
	if(belong[l]==belong[r]) return bl(belong[l],l,r,x);
	else{
		x=bl(belong[l],l,R[belong[l]],x);
		for(int i=belong[l]+1;i<=belong[r]-1;i++) qp[i].push(x),qp2[i].push(x),x=qp[i].top(),qp[i].pop();
		return bl(belong[r],L[belong[r]],r,x);
	}
}

signed main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>m;block=sqrt(n);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		belong[i]=ceil(1.0*i/block);
	}
	for(int i=1;i<=belong[n];i++){
		L[i]=R[i-1]+1,R[i]=i*block;
		for(int j=L[i];j<=R[i];j++) qp[i].push(a[j]);
	}
	R[belong[n]]=n;
	while(m--){
		int l,r,x;
		cin>>l>>r>>x;
		if(l>r) cout<<query(1,r,query(l,n,x))<<endl;
		else cout<<query(l,r,x)<<endl;
	}
	return 0;
}

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

文章操作

相关推荐

评论

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