专栏文章

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

jjerry1717
P14400题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minc0reg
此快照首次捕获于
2025/12/01 23:56
3 个月前
此快照最后确认于
2025/12/01 23:56
3 个月前
查看原文

题意

给定一个长为 nn 的环，然后有 qq 次操作，每次操作给定一个 xx，然后从 ll 遍历到 rr，若遍历到的元素大于 xx，就交换 xx 与遍历到的元素，每次操作输出最后的 xx。

题解

好可爱的分块题。
首先把环拆开，然后就相当于在区间上进行操作。
不难注意到假设当前区间没有被操作过，那么你最后的 xx 一定是这个区间的最大值或一开始给定的 xx，然后对于子任务 2 就很简单了：维护一个大根堆，对于每次操作比较堆顶和 xx，若 xx 大则不管，否则把堆顶取出来输出，把 xx 放进去。
可以发现在这个做法中你并不在意每个值具体位于那个位置，我们只知道序列上到底存在那些值。
然后考虑如何把这个做法搬到区间上，可以使用分块。
对于每一个块，维护一个全局做法，然后如果每次询问整块就做完了。
困难的是如何应对散块的部分，我们发现一个区间先插 xx 后插 yy 与先插 yy 后插 xx 是完全一样的，都是只有更小的值会被留下。
这提示我们对于每一个块对曾经的修改开一个小根堆，然后对于散块操作从左往右扫一遍，用堆顶与当前值比较。注意到若当前的值被换了还会影响后面的值，所以把当前值（如果被交换了）也插进堆里，然后对块暴力修改并统计答案即可。
对于复杂度，因为散块和整块都有堆，所以 log⁡\log 平衡不掉，直接是 O(nnlog⁡n)\mathcal O(n \sqrt n \log n) 的。

代码

注意，为了避免杂七杂八的分类讨论，可以在堆里插哨兵。
CPP
#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));
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...