Loj 2736 回转寿司

Posted on | Views:

分块 + 堆.

每次操作后,如果区间内最大值 $>A$ , $A$ 就会变成区间内的最大值,并且某些数的位置会变,否则无事发生.

考虑分块,对于整块部分,对每块开一个大根堆维护块内所有元素.

修改时,若块内最大值 $>A$ ,就将把 $A$ 换成它,并且打上标记,表示这一块被元素 $A$ 进行了一次操作.

对于边角部分,修改时将标记下放,然后暴力重构这一块.

按照遍历的顺序从前往后依次处理,每一块 $A​$ 被交换后的值就是下一块 $A​$ 的初始值.

唯一的问题在于某一块已经有标记时,再加入标记需要怎样处理.

首先注意到,操作的顺序不会影响块内元素最后的值,于是没必要合并标记,可以都存下来,下放标记时一起处理.

每个数显然只可能被最小的数替换一次,后面的都没用了,于是用小根堆来存储标记,下放时用堆顶不断尝试交换.

时间复杂度 $O(n\sqrt n\log \sqrt n)$ ,空间复杂度 $O(n\sqrt n)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//%std
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
struct Greater
{
	priority_queue<int> Heap;
	void push(int x){Heap.push(x);}
	int top(){return Heap.top();}
	void pop(){Heap.pop();}
	bool empty(){return Heap.empty();}
};
struct Less
{
	priority_queue<int> Heap;
	void push(int x){Heap.push(-x);}
	int top(){return -Heap.top();}
	void pop(){Heap.pop();}
	bool empty(){return Heap.empty();}
};
const int MAXN=4e5+10,S=633;
int n,m,B,bel[MAXN],a[MAXN],lp[S],rp[S];
Greater val[S];
Less tag[S];
void pushdown(int x)
{
	if(!tag[x].empty())
	{
		for(int i=lp[x];i<=rp[x];++i)
			if(a[i]>tag[x].top())
			{
				tag[x].push(a[i]);
				a[i]=tag[x].top();
				tag[x].pop();
			}
		while(!tag[x].empty())
			tag[x].pop();
	}
}
void bf(int L,int R,int &A)
{
	int x=bel[L];
	pushdown(x);
	for(int i=L;i<=R;++i)
		if(a[i]>A)
			swap(a[i],A);
	while(!val[x].empty())
		val[x].pop();
	for(int i=lp[x];i<=rp[x];++i)
		val[x].push(a[i]);
}
void upd(int L,int R,int &A)
{
	if(bel[L]==bel[R])
		bf(L,R,A);		
	else
	{
		bf(L,rp[bel[L]],A);
		for(int i=bel[L]+1;i<=bel[R]-1;++i)
			if(val[i].top()>A)
			{
				tag[i].push(A);
				val[i].push(A);
				A=val[i].top();
				val[i].pop();
			}
		
		bf(lp[bel[R]],R,A);
	}
}
int main()
{
	n=read(),m=read();
	B=sqrt(n);
	for(int i=1;i<=n;++i)
	{
		a[i]=read();
		bel[i]=(i-1)/B+1;
		lp[bel[i]]=(bel[i]-1)*B+1;
		rp[bel[i]]=lp[bel[i]]+B-1;
		val[bel[i]].push(a[i]);
	}
	rp[bel[n]]=n;
	for(int i=1;i<=m;++i)
	{
		int L=read(),R=read(),A=read();
		if(L<=R)
			upd(L,R,A);
		else
		{
			upd(L,n,A);
			upd(1,R,A);
		}
		printf("%d\n",A);
	}
	return 0;
}