题目链接

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int SZN = 1e5 + 5;
const int SZM = 350; // sqrt(SZN)
int n, l, r, c, num, tot;
int a[SZN], t[SZN], s[SZM], st[SZM], ed[SZM], belong[SZN];
void Down (int x) {
	if (s[x] == INF) return;
	for (int i = st[x]; i <= ed[x]; i++) a[i] = s[x];
	s[x] = INF;
}
int solve (int l, int r, int c) {
	int sid = belong[l], eid = belong[r], ans = 0;
	Down(sid), Down(eid);
	if (sid == eid) {
		for (int i = l; i <= r; i++) {
			if (a[i] == c) ans++;
			else a[i] = c;
		}
		// Sort(sid);
		return ans;
	}
	for (int i = l; belong[i] == sid; i++) {
		if (a[i] == c) ans++;
		else a[i] = c;
	}
	for (int i = sid + 1; i < eid; i++) {
		if (s[i] == c) {
			ans += ed[i] - st[i] + 1;
			continue;
		}
		if (s[i] != INF) {
			s[i] = c;
			continue;
		}
		for (int j = st[i]; j <= ed[i]; j++) 
			if (a[j] == c) ans++;
		s[i] = c;
	}
	for (int i = r; belong[i] == eid; i--) {
		if (a[i] == c) ans++;
		else a[i] = c;
	}
	return ans;
}
signed main(void)
{
	cin >> n;
	tot = num = sqrt(n);
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		t[i] = a[i];
	}
	for (int i = 1; i <= tot; i++)
		st[i] = (i - 1) * num + 1, ed[i] = i * num;
	if (num * num != n) {
		tot++;
		st[tot] = num * num + 1;
		ed[tot] = n;
	}
	for (int i = 1; i <= tot; i++) {
		s[i] = INF;
		for (int j = st[i]; j <= ed[i]; j++)
			belong[j] = i;
	}
	for (int i = 1; i <= n; i++) {
		cin >> l >> r >> c;
		if (l > r) swap(l, r);
		cout << solve(l, r, c) << endl;
	}
	return 0;
}

RT，这还能过？我的思路是块内二分，结果块内暴力水过了？

评测记录