分块求调

#include <bits/stdc++.h>
using namespace std;

const int _ = 3e5 + 5;

int n,blo;
int a[_];
int L[_],R[_],id[_],cov[_],covnum[_];

void Push(int x) {
  if(!cov[id[x]]) return;
  cov[id[x]] = 0;
  for(int i = L[id[x]];i <= R[id[x]];i++) a[i] = covnum[id[x]];
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0),cout.tie(0);
  cin >> n;
  blo = sqrt(n);
  for(int i = 1;i <= n;i++) {
  	cin >> a[i];
  }
  for(int i = 1;i <= blo;i++) {
  	L[i] = R[i - 1] + 1;
  	R[i] = n / blo * i;
  }
  if(R[blo] < n) blo++,L[blo] = R[blo - 1] + 1,R[blo] = n;
  for(int i = 1;i <= blo;i++) {
  	for(int j = L[i];j <= R[i];j++) {
  	  id[j] = i;
	}
  }
  for(int i = 1,l,r,c;i <= n;i++) {
  	cin >> l >> r >> c;
  	int ans = 0;
  	if(id[l] == id[r]) {
  	  for(int j = l;j <= r;j++) ans += (a[j] == c),a[j] = c;
	} else {
	  Push(l),Push(r);
	  for(int j = l;j <= R[id[l]];j++) {
	  	ans += (a[j] == c);
		a[j] = c;
	  }
	  for(int j = L[id[r]];j <= r;j++) {
	  	ans += (a[j] == c);
	  	a[j] = c;
	  }
  	  for(int j = id[l] + 1;j < id[r];j++) {
  	  	if(cov[j]) ans += (covnum[j] == c) * (R[j] - L[j] + 1);
  	  	else {
  	  	  for(int k = L[j];k <= R[j];k++) {
  	  	    ans += (a[k] == c);
		  }
		}
  	  	cov[j] = 1,covnum[j] = c;
	  }
	}
	cout << ans << '\n';
  }
  return 0;
}