关于分块

#include <bits/stdc++.h>
#define int long long
#define pb push_back

using namespace std;
const int maxn = 1e5 + 10, maxk = 4e2 + 10, inf = 1e10;

int n, m, len, a[maxn], pos[maxn];
struct node {
	int l, r, c;
}t[maxk];
vector<int> v[maxk];

void blk_init() {
	len = sqrt(n), m = (n % len ? len + 1 : len);
	for (int i = 1; i <= m; ++i) t[i] = {(i - 1) * len, i * len, inf};
	t[m].r = n;
	for (int i = 1; i <= m; ++i) {
		for (int j = t[i].l; i <= t[i].r; ++i) pos[j] = i, v[i].pb(a[j]);
		sort(v[i].begin(), v[i].end());
	}
}

void rebd(int u) {
	v[u].clear();
	for (int i = t[u].l; i <= t[u].r; ++i) v[u].pb(a[i]);
}

void modify(int l, int r, int c) {
	int pl = pos[l], pr = pos[r];
	if (pl == pr) {
		for (int i = l; i <= r; ++i) a[i] = c;
		rebd(pl);
		return;
	}
	for (int i = l; i <= t[pl].r; ++i) a[i] = c;
	rebd(pl);
	for (int i = t[pr].l; i <= r; ++i) a[i] = c;
	rebd(pr);
	for (int i = pl + 1; i <= pr - 1; ++i) t[i].c = c;
}

int query(int l, int r, int c) {
	int pl = pos[l], pr = pos[r], res = 0;
	if (pl == pr) {
		if (t[pl].c == c) return t[pl].r - t[pl].l + 1;
		for (int i = l; i <= r; ++i) res += (a[i] == c);
		return res;
	}
	if (t[pl].c == c) res += t[pl].r - l + 1;
	else for (int i = l; i <= t[pl].r; ++i) res += (a[i] == c);
	if (t[pr].c == c) res += r - t[pr].l + 1;
	else for (int i = t[pr].l; i <= r; ++i) res += (a[i] == c);
	for (int i = pl + 1, p1, p2; i <= pr - 1; ++i) {
		if (t[i].c == c) {
			res += t[i].r - t[i].l + 1;
			continue;
		}
		p1 = upper_bound(v[i].begin(), v[i].end(), c) - v[i].begin(); 
		p2 = lower_bound(v[i].begin(), v[i].end(), c) - v[i].begin();
		if (v[i][p2] != c) continue;
		res += p1 - p2;
	}
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	blk_init();
	for (int i = 1, l, r, c; i <= n; ++i) {
		cin >> l >> r >> c;
		cout << query(l, r, c) << '\n';
		modify(l, r, c);
	}
	return 0;
}