[COCI 2023/2024 #2] Zatopljenje 题解

闲话

考前集训，每日一练做到的题，我写挂了五次。自己想到分块的做法，看题解区没有，于是来发一篇。

思路

我们注意到，当海水高度为 时，区间 的小岛的个数可以这么计算：

所以第 个位置产生贡献当且仅当 ，考虑分块并预处理出每个块的答案。由于 ，所以要离散化。时间复杂度 ，虽然比不上线段树或树状数组，但是思路还是比较好想的。

具体细节见代码实现。

Tip : 不要开long long，不然会MLE。

Code

#include <bits/stdc++.h>
#define PII pair<int, int>
using namespace std;
template <typename _Tp>
inline void read(_Tp &x) {
	int neg = 1;
	char ch;
	while(ch = getchar(), !isdigit(ch)) if(ch == '-') neg = -1;
	x = ch - '0';
	while(ch = getchar(), isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ '0');
	x *= neg;
	return;
}
// bans[i][j] : 第 i 个块当 x = j 时的答案
int n, q, a[200005], blk, cnt, bans[505][200005], x, l, r;
PII p[200005];
signed main() {
	read(n), read(q);
	for(int i = 1; i <= n; ++i) read(a[i]);
	// 加一个 0 ，方便离散化
	a[0] = 0, ++n;
	// 离散化
	for(int i = 0; i < n; ++i) p[i] = {a[i], i};
	sort(p, p + n);
	for(int i = 0; i < n; ++i) {
		if(i == 0) a[p[i].second] = 1;
		else {
			if(p[i].first == p[i - 1].first) a[p[i].second] = a[p[i - 1].second];
			else a[p[i].second] = a[p[i - 1].second] + 1;
		}
	}
	// 分块
	blk = sqrt(n);
	cnt = (n - 1) / blk + 1;
	for(int i = 0; i < n - 1; ++i) if(a[i] < a[i + 1]) {
			// 差分计算答案
			++bans[i / blk][a[i]];
			--bans[i / blk][a[i + 1]];
		}
	// 前缀和
	for(int i = 0; i < cnt; ++i) for(int j = 1; j <= n; ++j) bans[i][j] += bans[i][j - 1];
	while(q--) {
		read(l), read(r), read(x);
		// 对 x 离散化，找到最后一个小于等于 x 的值
		int ind = lower_bound(p, p + n, (PII){x + 1, 0}) - p, ans;
		x = a[p[ind - 1].second];
		// l 点的答案
		ans = a[l] > x;
		if(l / blk == r / blk) {
			// 在同一个块中
			for(int i = l; i < r; ++i) ans += (a[i] <= x && a[i + 1] > x);
		}
		else {
			// 计算 l 所在块的答案
			for(int i = l; i < (l / blk + 1) * blk; ++i) ans += (a[i] <= x && a[i + 1] > x);
			// 计算 r 所在块的答案
			for(int i = r / blk * blk; i < r; ++i) ans += (a[i] <= x && a[i + 1] > x);
			// 计算中间块的答案
			for(int i = l / blk + 1; i < r / blk; ++i)ans += bans[i][x];
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Submisson

---

完结撒花！！！✿✿ヽ(°▽°)ノ✿