數顔色 / 維護隊列
題目連結：ybt金牌導航6-3-4 / luogu P1903
題目大意
給你一個序列，要你支援一些操作：
把一個數換成另一個數，查詢一個區間中有多少個不同的數。
思路
我們考慮用分塊來做。
那我們要先知道如何判斷這個數在某一塊中是否是第一次出現。
我們可以搞一個 b e f i bef_i befi 記錄跟這個數一樣的它前面的最後一個數是哪裡。
那如果 b e f i < l bef_i<l befi<l，那它就是在 l l l 後面的這個塊中第一次出現。
那不難想到要怎麼暴力搞，那我們接着看整塊怎麼搞。
不難想到排序之後二分。
那接着看修改。發現修改之後有三個東西會影響：
- 後面第一個跟它原來顔色的數（ b e f bef bef 值是 x x x 的數）
- 後面第一個跟它新的顔色的數（ b e f bef bef 将要是 x x x 的數）
- 前面第一個跟它新的顔色的數（ x x x 的 b e f bef bef 将要是它）
那修改它們的 b e f bef bef 不難想到怎麼搞，但問題是如何找到。
如果在塊内，我們可以直接暴力找。跑出塊之後，我們就一個一個塊的找，不難想到可以通過二分判斷一個數是否在一個塊中。（把塊中數排序）
然後搞搞就行了，代碼比較多，煩，可以看看代碼具體實作。
然後由于 luogu 需要卡常，我快讀加了之後，還加了一個優化：
當修改 b e f bef bef 的時候我們不要直接就把那塊重新排序，而是打個标記。
然後到時我們二分之前，如果有标記，就再排序，然後清空标記。
（這樣可以幾次修改才排一次序，讓排序次數最小）
代碼
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, m, a[200001], S, s;
int bl[10001], br[10001], x, y;
int lst[1000001], bef[200001];
int aa[200001], beff[200001];
bool nc[200001];//小小的優化，修改之後先不直接更新排序，要用的時候要修改才修改
char op;
int read() {
int re = 0, zf = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') zf = -zf;
c = getchar();
}
while (c >= '0' && c <= '9') {
re = (re << 3) + (re << 1) + c - '0';
c = getchar();
}
return re * zf;
}
void Sort(int x) {//求排序
for (int i = bl[x]; i <= br[x]; i++)
aa[i] = a[i], beff[i] = bef[i];
sort(aa + bl[x], aa + br[x] + 1);
sort(beff + bl[x], beff + br[x] + 1);
nc[x] = 0;
}
void premake() {
for (int i = 1; i <= n; i++) {
if (i % S == 1) {
br[s] = i - 1;
bl[++s] = i;
}
}
br[s] = n;
bl[s + 1] = br[s + 1] = n + 1;
for (int i = 1; i <= s; i++) {
nc[i] = 1;
}
}
int query(int block, int x) {//找這一塊有多少個數的 bef 值小于 x
if (nc[block]) Sort(block);
int l = bl[block], r = br[block], ans = bl[block] - 1;
while (l <= r) {
int mid = (l + r) >> 1;
if (beff[mid] < x) ans = mid, l = mid + 1;
else r = mid - 1;
}
return ans - bl[block] + 1;
}
bool find(int block, int x) {//找這一塊中有沒有 x 這個數
if (nc[block]) Sort(block);
int l = bl[block], r = br[block];
while (l <= r) {
int mid = (l + r) >> 1;
if (aa[mid] == x) return 1;
if (aa[mid] < x) l = mid + 1;
else r = mid - 1;
}
return 0;
}
int work(int l, int r) {//查詢
int L = (l - 1) / S + 1;
int R = (r - 1) / S + 1;
int re = 0;
if (r - l + 1 <= 2 * S) {
for (int i = l; i <= r; i++)
if (bef[i] < l) re++;
return re;
}
if (l == bl[L]) L--; if (r == br[R]) R++;
for (int i = L + 1; i < R; i++) re += query(i, l);//整塊
for (int i = l; i <= br[L]; i++) if (bef[i] < l) re++;//兩邊
for (int i = bl[R]; i <= r; i++) if (bef[i] < l) re++;
return re;
}
void kill(int x) {//處理後面第一個跟它原來顔色的數（bef 值是 x 的數）
int in = (x - 1) / S + 1;
for (int i = x + 1; i <= br[in]; i++)
if (bef[i] == x) {
bef[i] = bef[x];
nc[in] = 1;
return ;
}
for (int i = in + 1; i <= s; i++) {
if (find(i, a[x])) {
for (int j = bl[i]; j <= br[i]; j++)
if (a[j] == a[x]) {
bef[j] = bef[x];
nc[i] = 1;
return ;
}
}
}
}
void change1(int x, int y) {//處理後面第一個跟它新的顔色的數（bef 将要是 x 的數）
int in = (x - 1) / S + 1;
for (int i = x + 1; i <= br[in]; i++)
if (a[i] == a[x]) {
bef[i] = x;
nc[in] = 1;
return ;
}
for (int i = in + 1; i <= s; i++) {
if (find(i, a[x])) {
for (int j = bl[i]; j <= br[i]; j++)
if (a[j] == a[x]) {
bef[j] = x;
nc[i] = 1;
return ;
}
}
}
}
void change2(int x, int y) {//找到前面第一個跟它新的顔色的數（x 的 bef 将要是它）
int in = (x - 1) / S + 1;
for (int i = x - 1; i >= bl[in]; i--)
if (a[i] == a[x]) {
bef[x] = i;
nc[in] = 1;
return ;
}
for (int i = in - 1; i >= 1; i--)
if (find(i, a[x])) {
for (int j = br[i]; j >= bl[i]; j--)
if (a[j] == a[x]) {
bef[x] = j;
nc[in] = 1;
return ;
}
}
bef[x] = 0;
nc[in] = 1;
}
void change(int x, int y) {
change1(x, y);
change2(x, y);
}
int main() {
n = read(); m = read();
for (int i = 1; i <= n; i++) {
a[i] = read();
bef[i] = lst[a[i]];
lst[a[i]] = i;
}
S = sqrt(n);
premake();
while (m--) {
op = getchar();
while (op != 'Q' && op != 'R') op = getchar();
if (op == 'Q') {
x = read(); y = read();
printf("%d\n", work(x, y));
continue;
}
if (op == 'R') {
x = read(); y = read();
if (a[x] == y) continue;
kill(x);
a[x] = y;
change(x, y);
continue;
}
}
return 0;
}