「Solution」「JOISC 2016 Day 3」回转寿司

人生第二道黑题分块好题

link](https://loj.ac/p/2736))

Solution

不难看出，在遍历完区间之后，若该区间有数大于$A$，那么$A$将进入该区间，并弹出区间内最大的数。

这里用到一个结论，序列操作的顺序不会改变数列中数字的最终集合。

先咕了。

给一个证明：

设有两个操作：$(l_1,r_1,A_1)$和$(l_2,r_2,A_2)$并假定$A_1>A_2$。

• 当$[l_1,r_1] \bigcup [l_2,r_2] = \varnothing$时，两个操作一定不会影响
• 当$[l_1,r_1] \bigcup [l_2,r_2] \neq \varnothing$时，若先操作$(l_1,r_1,A_1)$，设弹出了$A^{'}$，若$A^{'}>A_2$，那么

咕咕咕。

#include <cmath>
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 4e5 + 5;
const int MAXLOG = 650;

int n, m, siz, cnt, block[MAXN], a[MAXN];
priority_queue<int, vector<int>, less<int> > now[MAXLOG];
priority_queue<int, vector<int>, greater<int> > his[MAXLOG];

void reset(int id) {
	for (int i = (id - 1) * siz + 1; i <= id * siz; i++) {
		his[id].push(a[i]);
		a[i] = his[id].top();
		his[id].pop();
	}
	while (his[id].size()) his[id].pop();
}

void update(int id) {
	while (now[id].size()) {
		now[id].pop();
	}
	for (int i = (id - 1) * siz + 1; i <= id * siz; i++) {
		now[id].push(a[i]);
	}
}

int feces(int l, int r, int val) {
	reset(block[l]);
	for (int i = l; i <= min(block[l] * siz, r); i++) {
		if (a[i] > val) swap(a[i], val);
	}
	for (int i = block[l] + 1; i < block[r]; i++) {
		his[i].push(val);
		now[i].push(val);
		val = now[i].top(); 
		now[i].pop();
	}
	update(block[l]);
	if (block[l] != block[r]) {
		reset(block[r]);
		for (int i = (block[r] - 1) * siz + 1; i <= r; i++) {
			if (a[i] > val) swap(a[i], val);
		}
		update(block[r]);
	}
	return val;
}

int main() {
	scanf("%d %d", &n, &m);
	siz = sqrt(n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		block[i] = (i - 1) / siz + 1;
		now[block[i]].push(a[i]);
	}
	for (int t = 1, l, r, val; t <= m; t++) {
		scanf("%d %d %d", &l, &r, &val);
		if (l > r) {
			printf("%d\n", feces(1, r, feces(l, n, val)));
		} else printf("%d\n", feces(l, r, val));
	}
	return 0;
}