P1903 [国家集训队]数颜色 / 维护队列

带修改莫队板子

块长取 (O(n^{frac 2 3}))
总时间复杂度为 (O(n^{frac 5 3}))

( ext{Code})

#include <cstdio> 
#include <cmath>
#include <algorithm>
#include <iostream>
#define re register
using namespace std;

const int N = 133343;
int n, m, q1, q2, len, color, buc[1000005], a[N], aa[N], ans[N];
struct node1{int l, r, id, f;}Q[N];
struct node2{int x, y, z;}mf[N];

inline bool cmp(node1 a, node1 b)
{
	return ((a.l/len == b.l/len) ? ((a.r/len == b.r / len) ? (a.id < b.id) : (a.r < b.r)) : (a.l < b.l));
}
inline void add(int x){if (!buc[x]) ++color; ++buc[x];}
inline void del(int x){--buc[x]; if (!buc[x]) --color;}
inline void read(int &x)
{
	x = 0; char ch = getchar(); int f = 1;
	while (!isdigit(ch)) f = (ch == '-' ? -1 : f), ch = getchar();
	while (isdigit(ch)) x = (x<<3) + (x<<1) + (ch ^ 48), ch = getchar();
	x *= f;
}

int main()
{
	read(n), read(m);
	for(re int i = 1; i <= n; i++) read(a[i]), aa[i] = a[i];
	int l, r, lst; char op[3];
	for(re int i = 1; i <= m; i++)
	{
		scanf("%s", op), read(l), read(r);
		if (op[0] == 'Q') ++q1, Q[q1] = (node1){l, r, q1, q2};
		else mf[++q2] = (node2){l, r, aa[l]}, aa[l] = r;
	}
	len = pow((double)n, 2 / 3.0), sort(Q + 1, Q + q1 + 1, cmp), l = r = lst = 0;
	for(re int i = 1; i <= q1; i++)
	{
		for(; lst < Q[i].f; ++lst)
		{
			if (l <= mf[lst + 1].x && mf[lst + 1].x <= r) del(mf[lst + 1].z), add(mf[lst + 1].y);
			a[mf[lst + 1].x] = mf[lst + 1].y;
		}
		for(; lst > Q[i].f; --lst)
		{
			if (l <= mf[lst].x && mf[lst].x <= r) del(mf[lst].y), add(mf[lst].z);
			a[mf[lst].x] = mf[lst].z;
		}
		for(; l > Q[i].l; l--) add(a[l - 1]);
		for(; l < Q[i].l; l++) del(a[l]);
		for(; r < Q[i].r; r++) add(a[r + 1]);
		for(; r > Q[i].r; r--) del(a[r]);
		ans[Q[i].id] = color;
	}
	for(re int i = 1; i <= q1; i++) printf("%d
", ans[i]);
}