[bzoj 2120] 数颜色: 带修改莫队算法

长度为n的正整数序列, m条指令. 每条指令询问区间[l, r]中共有多少种不同的数, 或将第p个数修改为c. (n,m≤10^5, 修改操作不多于10^3次, 所有整数属于[1,10^6]) 可以BIT套线段树, 可以分块, 个人觉得还是莫队最优雅.

网上许多将莫队称作暴力......我觉得不是很暴力啊......暴力美学?

倒是觉得BIT套线段树最暴力, 虽然复杂度很优.

莫队算法的复杂度分析见[WC 2013] 糖果公园.

可以yy一下......k维莫队的时间复杂度是 (假设n和询问q同阶). 理论上来说, 总是有一种优于暴力的做法......

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;

const int MAX_N = 1e4, MAX_M = 1e4, MAX_A = 1e6, MAX_R = 1e3;

int n, now, b[MAX_N], A[MAX_N], ans[MAX_M], cnt[MAX_A + 1];

struct Op {
	int p, x, y;
} O[MAX_R];
struct Qr {
	int k, l, r, t;
	bool operator<(const Qr& rhs) const
	{
		return b[l] < b[rhs.l] || (b[l] == b[rhs.l] && b[r] < b[rhs.r])
			|| (b[l] == b[rhs.l] && b[r] == b[rhs.r] && t < rhs.t);
	}
} Q[MAX_M];

inline void add(int v)
{
	if (!cnt[v]) ++now;
	++cnt[v];
}

inline void remove(int v)
{
	--cnt[v];
	if (!cnt[v]) --now;
}

inline void perform(int t, int l, int r)
{
	int p = O[t].p, y = O[t].y;
	if (p >= l && p <= r) {
		remove(A[p]);
		add(y);
	}
	A[p] = y;
}

inline void cancel(int t, int l, int r)
{
	int p = O[t].p, x = O[t].x;
	if (p >= l && p <= r) {
		remove(A[p]);
		add(x);
	}
	A[p] = x;
}

void init()
{
	int sz = 1, nn = n*n;
	while (sz*sz*sz < nn) ++sz;
	for (int i = 0, k = 0; k < n; ++i)
		Rep (j, 0, min(sz, n-k))
			b[k++] = i;
}

int main()
{
	int m, p = 0, q = 0;
	scanf("%d%d", &n, &m);
	init();
	
	Rep (i, 0, n)
		scanf("%d", &A[i]);
	Rep (i, 0, m) {
		char o;
		int a, b;
		scanf(" %c%d%d", &o, &a, &b);
		--a;
		if (o == 'Q') {
			--b;
			Q[q] = (Qr){q, a, b, p-1};
			++q;
		} else {
			O[p] = (Op){a, A[a], b};
			A[a] = b;
			++p;
		}
	}
	Down (i, p-1, 0)
		A[O[i].p] = O[i].x;

	sort(Q, Q+q);

	int l = Q[0].l, r = l - 1, t = -1;
	Rep (i, 0, q) {
		while (t < Q[i].t)
			perform(++t, l, r);
		while (t > Q[i].t)
			cancel(t--, l, r);
		while (r < Q[i].r)
			add(A[++r]);
		while (l > Q[i].l)
			add(A[--l]);
		while (r > Q[i].r)
			remove(A[r--]);
		while (l < Q[i].l)
			remove(A[l++]);
		ans[Q[i].k] = now;
	}

	Rep (i, 0, q)
		printf("%d\n", ans[i]);

	return 0;
}