洛谷 P1903 [国家集训队]数颜色

题意简述

给定一个数列，支持两个操作

1.询问l~r有多少不同数字

2.修改某个数字

题解思路

带修莫队

如果修改多了，撤销修改

如果修改少了，进行修改

代码

#include <cmath>

#include <iostream>

#include <algorithm>

using namespace std;

struct Query

{

	int l, r, t, i;

} qu[51000];

struct Modify

{

	int p, col;

} mo[51000];

int n, m, cnt1, cnt2, len, s, l = 1, r, t;

int a[51000], c[1001000], ans[51000], tti[51000];

char opt;

bool cmp(const Query &x, const Query &y)

{

	if (x.l / len != y.l / len) return x.l / len < y.l / len;

	if (x.r / len != y.r / len) return x.r / len < y.r / len;

	return x.t < y.t;

}

void add(int x) {s += !(c[x]++); }

void del(int x) {s -= !(--c[x]); }

void replace(int x)

{

	int xx = mo[tti[t]].p;

	if (xx >= l && xx <= r)

	{

		s -= !(--c[a[mo[tti[t]].p]]);

		s += !(c[mo[tti[t]].col]++);

	}

	swap(a[mo[tti[t]].p], mo[tti[t]].col);

}

int main()

{

	ios::sync_with_stdio(false);

	cin >> n >> m;

	for (register int i = 1; i <= n; ++i) cin >> a[i];

	for (register int i = 1; i <= m; ++i)

	{

		cin >> opt;

		if (opt == 'Q')

		{

			++cnt1;

			cin >> qu[cnt1].l >> qu[cnt1].r;

			qu[cnt1].t = i;

			qu[cnt1].i = cnt1;

		}

		else

		{

			++cnt2;

			cin >> mo[cnt2].p >> mo[cnt2].col;

			tti[i] = cnt2;

		}

	}

	len = n * pow(cnt2, 1.0 / 3);

	len = pow(n, 2.0 / 3);

	sort(qu + 1, qu + cnt1 + 1, cmp);

	for (register int i = 1; i <= cnt1; ++i)

	{

		while (l > qu[i].l) add(a[--l]);

		while (r < qu[i].r) add(a[++r]);

		while (l < qu[i].l) del(a[l++]);

		while (r > qu[i].r) del(a[r--]);

		while (t < qu[i].t) if (tti[++t]) replace(t);

		while (t > qu[i].t) if (tti[--t]) replace(t);

		ans[qu[i].i] = s;

	}

	for (register int i = 1; i <= cnt1; ++i) cout << ans[i] << endl;

}