回转寿司——有趣的分块_c++寿司盘子颜色 题目

样例1输入： 
6 7
8 6 7 4 5 9
2 4 5
4 1 4
6 2 7
1 5 2
3 4 8
4 3 1
3 1 3
样例1输出：
7
9
8
7
8
6
5 
样例1每次提供完新寿司后，顾客拥有的寿司价格依次为：
1.8 5 6 4 5 9
2.8 5 6 4 4 5
3.7 5 6 4 4 5
4.2 5 6 4 4 5
5.2 5 6 4 4 5
6.2 5 5 1 4 4

7.2 5 3 1 4 4 

样例2输入：
4 2
5 2 4 7
1 4 3
1 4 1
样例2输出：
7
5
 
样例3输入：
10 10
19 5 8 17 14 3 9 10 7 6
1 8 4
7 3 2
5 9 10
4 8 3
10 3 6
8 7 4
6 6 3
2 9 12
6 3 7
9 6 3
样例3输出：
19
10
14
17
8
10
3
12
7

9

n<=40w,q<=2.5w，时限4s

很有意思的一道题。区间问题除了线段树等数据结构之外，一般用分块和莫队解决，而这道题有在线操作的意味，因此后者pass~

考虑分块，显然，每一次进入区间后，寿司的数量是不会变的，而且，寿司滚出这个区间之后显然是这段区间+新寿司中的最大值，因此我们可以用大根堆来维护每一个块的最大值，那么每一个块滚出寿司最大值之后，最后滚出的寿司必然也是最大值。

整块搞好了，那么如何处理散块呢？只有散块我们需要具体的值，所以我们可以像线段树一样向块打标记，等到成为散块处理的时候再更新。因为是按顺序滚的，而且每个人都会选择最小值，所以我们用小根堆维护。

至此，小根堆+大根堆+分块完美解决，时间复杂度q√nlogn

……值得注意的是，直接用stl会炸，因此我们需要一些优化~详见代码

#include<bits/stdc++.h>
using namespace std;
const int N = 4e5+10,M = 25010,Maxsiz = 637; 
#define Inc(i,L,r) for(register int i=(L);i<=(r);++i)
int n,Q,a[N];
int siz,bl[N];
vector<int>vec[Maxsiz];//记录修改操作 
priority_queue<int>Max[Maxsiz];//大根堆 
inline void construct(int idx){
	Max[idx]=priority_queue<int>(a+(idx-1)*siz+1,a+min(idx*siz,n)+1);//重构操作就是重新把一段区间塞进去，要比单纯的push()pop()快？ 
}
inline void init(){
	scanf("%d%d",&n,&Q);
	Inc(i,1,n)scanf("%d",&a[i]);
	siz=sqrt(n);
	Inc(i,1,n)bl[i]=(i-1)/siz+1;
	Inc(i,1,n)Max[bl[i]].push(a[i]);//初始化块的最大值
}
inline void update(int idx){//我们注意到，每次只会流动一个，是不是和线段树的标记下传很像？
	if(vec[idx].empty())return ;
	priority_queue<int,vector<int>,greater<int> >Min(vec[idx].begin(),vec[idx].end());
	Inc(i,(idx-1)*siz+1,min(idx*siz,n)){
		int HeapTop=Min.top();
		if(a[i]>HeapTop)Min.pop(),Min.push(a[i]),a[i]=HeapTop;
	}
	construct(idx);
	vec[idx].clear();
}
inline int Query(int L,int r,int k){
	int ret=k;
	if(bl[r]-bl[L]<=1){
		update(bl[L]);//只有处理散块的时候，我们才更新 
		if(bl[r]^bl[L])update(bl[r]);
		Inc(i,L,r)if(a[i]>ret)swap(a[i],ret);
		construct(bl[L]);
		if(bl[r]^bl[L])construct(bl[r]);
	}else {
		update(bl[L]);
		Inc(i,L,bl[L]*siz)if(a[i]>ret)swap(a[i],ret);
		construct(bl[L]);
		
		Inc(i,bl[L]+1,bl[r]-1){ 
			vec[i].push_back(ret);//我们假装把寿司扔进这个块里让它滚一遍
			int tmp=ret;
			Max[i].push(tmp);
			ret=Max[i].top();//最大的会滚出来 
			Max[i].pop();
		}
		
		update(bl[r]);
		Inc(i,(bl[r]-1)*siz+1,r)if(a[i]>ret)swap(a[i],ret);
		construct(bl[r]);
	}return ret;
}
inline void solv(){
	while(Q--){
		int L,r,k;scanf("%d%d%d",&L,&r,&k);
		if(L<=r)cout<<Query(L,r,k)<<"\n";
		else cout<<Query(1,r,Query(L,n,k))<<'\n';
	}
}
int main(){
	init();
	solv();
	return 0;
}