【loj 2736】「JOISC 2016 Day 3」回转寿司【分块】

传送门

Solution

首先考虑如果所有区间都是([1,n])，那么每次我们只需要知道全局的最大值就行了，只需要维护一个大根堆，并不关心内部的数字的顺序。

考虑分块，然后对整块做出类似的处理

对每一个块用一个大根堆维护权值，那么在询问时遇到整块直接取出最大值，如果最大值大于(A)就将最大值取出来作为新的(A)，将(A)push进大根堆，同时打一个标记。

对于散块，我们希望能够根据块上的标记，直接暴力复原它的真是面貌：

考虑从左到右直接扫一遍，对于(a_i)，如果目前所有标记中最小的一个都比(a_i)大，那么(a_i)就可以保留，否则就将(a_i)替换为最小的标记，将(a_i)作为新的标记
因为标记的顺序时互不影响的，所以我们用一个小根堆维护标记即可

总复杂度为(mathcal O(Qsqrt{n}log(n)))，注意暴力跑散块时要修改维护的大根堆

Code

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+10;
const int S=650;
int n,q,a[N],bel[N],L[N],R[N],bl,k;
priority_queue<int,vector<int>,greater<int> > p[S];
priority_queue<int> v[S];
inline void work(int x){
	if(p[x].empty()) return;
	while(!v[x].empty()) v[x].pop();
	for(int i=L[x];i<=R[x];++i){
		if(p[x].top()<a[i]){
			int u=p[x].top();
			p[x].pop();
			p[x].push(a[i]);
			a[i]=u;	
		}
		v[x].push(a[i]);
	}
	while(!p[x].empty()) p[x].pop();
}
inline void readd(int x){
	while(!v[x].empty()) v[x].pop();
	for(int i=L[x];i<=R[x];++i)
		v[x].push(a[i]);
}
inline int solve(int l,int r,int A){
	int fl=bel[l],fr=bel[r];
	if(fl==fr){
		work(fl);
		for(int j=l;j<=r;++j) if(a[j]>A) swap(a[j],A);
		readd(fl);
	}
	else{
		work(fl);
		for(int j=l;j<=R[fl];++j) if(a[j]>A) swap(a[j],A);
		readd(fl);
		for(int j=fl+1;j<fr;++j)
			if(v[j].top()>A){
				p[j].push(A);v[j].push(A);
				A=v[j].top();v[j].pop();
			}
		work(fr); 
		for(int j=L[fr];j<=r;++j) if(a[j]>A) swap(a[j],A);
		readd(fr);
	}
	return A;
}
int main(){
	scanf("%d%d",&n,&q);
	bl=pow(n,0.5);k=n/bl+1;
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]),bel[i]=(i-1)/bl+1,v[bel[i]].push(a[i]);
	for(int i=1;i<=k;++i)
		L[i]=(i-1)*bl+1,R[i]=min(i*bl,n);
	for(int i=1,l,r,A;i<=q;++i){
		scanf("%d%d%d",&l,&r,&A);
		if(l<=r) printf("%d
",solve(l,r,A));
		else{
			A=solve(l,n,A);
			printf("%d
",solve(1,r,A));
		}

	}
	return 0;
}