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

Description

给定序列 $a=(a_1,a_2,\cdots ,a_n)$，有 $m$ 个操作分两种：

• $\mathrm{modify}(i,x)$：执行 $a_i\leftarrow x$.
• $\mathrm{query}(l,r)$：求 ∣ { a l , a l + 1 , ⋯   , a r } ∣ |\{a_l,a_{l+1},\cdots,a_r\}| ∣{al​,al+1​,⋯,ar​}∣.

Limitations

$1\le n,m\le 133333$
$1\le a_i,x\le 10^6$
$2.5\text{s},512\text{MB}$

Solution

依然是不好直接做的询问，考虑莫队，维护 ${\text{cnt}}_i$ 表示当前区间内 $i$ 出现次数.
在 add 和 del 时更新 $\text{cnt}$，若一个数新出现或消失，我们更新答案.
但这里带了修改，我们给莫队直接加上时间维，每个查询多存一个 上次修改的时间戳.
然后需要修改与回溯函数.
拿修改讲，如果 $i$ 在当前区间内，那它就会影响答案，我们 del 掉原来的数，add 上新的即可.

有几点要提一下：

• 修改完后可以将 $a_i$ 和 $x$ 交换，下次遇到就是回溯，可以省一个函数.
• 不能用 map 维护 $\text{cnt}$，直接用数组.
• 要调块长，取 $B=n^{\frac{2}{3}}$ 可以过，笔者试了好几发.

Code

$1.79\text{KB},3.93\text{s},8.99\text{MB}\text{(in total, C++20 with O2)}$

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

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}
const int L = 1e6 + 10;
struct Modify { int pos, x; };
struct Query { int l, r, t, id; }; 

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, m;
	cin >> n >> m;
	vector<int> a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	
	vector<Modify> M;
	vector<Query> Q;
	for (int i = 0, x, y; i < m; i++) {
        char op;
		cin >> op >> x >> y, x--;
		if (op == 'R') M.push_back({x, y});
		else y--, Q.push_back({x, y, M.size() - 1, Q.size()});
	}
	
	const int B = pow(n, 2.0 / 3);
    sort(Q.begin(), Q.end(), [&](Query &a, Query &b) {
        if (a.l / B == b.l / B) {
    		if (a.r / B == b.r / B) return a.t < b.t;
    		return a.r / B < b.r / B;
    	}
    	return a.l / B < b.l / B;
    });
	
	array<int, L> cnt{};
	int ans = 0, l = 0, r = -1, t = -1;
	
	auto add = [&](int v) {
		if (cnt[v]++ == 0) ans++;
	};
	auto del = [&](int v) {
		if (--cnt[v] == 0) ans--;
	};
	auto upd = [&](int t, int l, int r) {
		auto &[pos, x] = M[t];
		if (l <= pos && pos <= r) del(a[pos]), add(x);
		swap(a[pos], x);
	};
	
	vector<int> res(Q.size());
	for (auto [ql, qr, qt, id] : Q) {
		while (ql < l) add(a[--l]);
        while (r < qr) add(a[++r]);
        while (l < ql) del(a[l++]);
        while (qr < r) del(a[r--]);
        while (t < qt) upd(++t, l, r);
        while (qt < t) upd(t--, l, r);
        res[id] = ans;
	}
	
	for (int i = 0; i < Q.size(); i++) cout << res[i] << endl;

	return 0;
}