题解：AT_joisc2016_h 回転寿司

环，直接将

l>r

的询问拆成两个询问做即可。

考虑到一次询问后，若有过交换，

x

一定是区间最大值。

说明区间中的最大值被取出，

x

被丢进去了。

如果询问都是全局的，可以发现其实我们连

x

被放在哪里都不关心，只需维护一个大根堆就可以做。

考虑分块。类比全局，整块是简单的。但是散块我们需要知道元素的顺序。

直接维护做不到，但我们可以根据之前对这个块的整块修改重构这个块。具体来说，维护修改

x

的小根堆然后从左往右扫每次取最小和当前

a_i

比较做交换。

CPP

#include<bits/stdc++.h>
#define rd read()
#define gc pa == pb && (pb = (pa = buf) + fread(buf, 1, 100000, stdin), pa == pb) ? EOF : *pa++
using namespace std;
static char buf[100000], * pa(buf), * pb(buf);
inline int read(){
	register int x=0,s=gc;while(!isdigit(s))s=gc;
	while(isdigit(s))x=(x<<1)+(x<<3)+(s^48),s=gc;
	return x;
}
const int N=400005,blk=600,S=N/blk+5;
int n,m,tot,L[S],R[S];
int a[N],bl[N];
priority_queue<int> q[S],p[S];
inline void push(int id,int &x){
	if(q[id].top()>x){
		int X=q[id].top();
		p[id].push(-x),q[id].pop(),q[id].push(x),x=X;
	}
}
inline void reb(int id){
	if(p[id].size()){
		for(int i=L[id];i<=R[id];++i)
			if(a[i]>-p[id].top()){
				int X=-p[id].top();
				p[id].pop(),p[id].push(-a[i]),a[i]=X;
			}
		while(p[id].size())p[id].pop();
	}
	while(q[id].size())q[id].pop();
	for(int i=L[id];i<=R[id];++i)q[id].push(a[i]);
}
inline void ask(int l,int r,int &x){
	if(bl[l]==bl[r]){
		reb(bl[l]);
		for(int i=l;i<=r;++i)if(a[i]>x)swap(a[i],x);
		return reb(bl[l]);
	}
	ask(l,R[bl[l]],x);
	for(int i=bl[l]+1;i<bl[r];++i)push(i,x);
	ask(L[bl[r]],r,x);
}
signed main()
{
	n=rd,m=rd,tot=(n-1)/blk+1;for(int i=1;i<=n;bl[i]=(i-1)/blk+1,++i)a[i]=rd;
	for(int i=1;i<=tot;++i)L[i]=R[i-1]+1,R[i]=i*blk;R[tot]=n;
	for(int i=1;i<=n;++i)q[bl[i]].push(a[i]);
	for(int i=1,l,r,x;i<=m;++i)l=rd,r=rd,x=rd,
		l>r?ask(l,n,x),ask(1,r,x):ask(l,r,x),cout<<x<<'\n';
	return 0;
}

题解：AT_joisc2016_h 回転寿司

文章操作

相关推荐

评论

题解：AT_joisc2016_h 回転寿司