纯分块求改，40pts，只过末三个点

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

这个wa有一个很神奇的性质，每一个点错误的数字都是比答案数字少1（

思路

$a_i$是颜色 我们发现只要 $pre_i$（位置 $i$ 的上一个颜色相同的位置）小于 $l$ ，那么该位置的颜色就是第一次在 $[l, r]$ 区间中出现的。
然后这题的做法可以转化为教主的魔法类似的做法

查询

• 对于整块对已排序数组lower_bound，在 $l$ 之前的都是答案
• 对于散块遍历，$pre_i$ 小于 $l$ 即可累加答案

修改

• 类似于题解第二页的暴力 $O(n)$ 修改已经在改完题目数据范围后被卡掉了
• 修改的时候同时是要更改 $pre_i$ 的，为了方便，同时维护了一个数组 $nxt_i$ （位置 $i$ 的下一个颜色相同的位置），这样修改 $pre$ 和 $nxt$ 的操作就类似于链表删点和插入
  这里维护一个set数组，对于每种颜色存放该颜色的位置
  这样进行插入操作的时候就可以通过--lower_bound和upper_bound来在set数组中快速找到修改后颜色的前驱和后继，从而进行插入操作

代码

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;

constexpr const int RANGE = 1e6 + 1;
constexpr const int N = 1.4e5;
string opt;
int n, m, l, r, block, tot;
int a[N], pre[N], nxt[N], L[N], R[N], srt[N], be[N];
set<int> has[RANGE];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    block = sqrt(n), tot = (n + block - 1) / block;
    auto rb = [&](int k) {
        for (int i = L[k]; i <= R[k]; ++i) srt[i] = pre[i];
        sort(srt + L[k], srt + R[k] + 1);
    };

    // memset(nxt, 0x7f, sizeof nxt);
    for (int i = 1; i <= tot; ++i) {
        L[i] = (i - 1) * block + 1; R[i] = min(n, i * block);
        for (int j = L[i]; j <= R[i]; ++j) {
            be[j] = i;
            // if (not has[a[j]].empty()) pre[j] = *has[a[j]].rbegin();
            // else pre[j] = 0;
            has[a[j]].insert(0);
            pre[j] = *has[a[j]].rbegin();
            has[a[j]].insert(j);
            nxt[pre[j]] = j;
        }
        rb(i);
    }

    for (int _ = 1; _ <= m; ++_) {
        cin >> opt >> l >> r;
        if (opt[0] == 'Q') {
            int ans = 0;
            for (int i = l; i <= min(r, R[be[l]]); ++i) if (pre[i] < l) ++ans;
            if (be[l] != be[r]) 
                for (int i = L[be[r]]; i <= r; ++i) if (pre[i] < l) ++ans;
            for (int i = be[l] + 1; i <= be[r] - 1; ++i)
                ans += lower_bound(srt + L[i], srt + R[i] + 1, l) - srt - L[i];
            cout << ans << endl;
        } else {
            pre[nxt[l]] = pre[l];
            nxt[pre[l]] = nxt[l];
            has[a[l]].erase(l);

            a[l] = r;
            has[r].insert(0);
            // for (auto v : has[r]) cout << v << " "; cout << endl;
            int preid = *(--lower_bound(has[r].begin(), has[r].end(), l));
            int nxtid = *upper_bound(has[r].begin(), has[r].end(), l);
            has[r].insert(l);
            pre[l] = preid; nxt[l] = nxtid;
            nxt[preid] = l; pre[nxtid] = l;
            rb(be[l]); rb(be[preid]); rb(be[nxtid]);
            // cout << preid << " " << nxtid << endl;
            // for (int i = 1; i <= n; ++i) cout << pre[i] << " "; cout << endl;
            // for (int i = 1; i <= n; ++i) cout << nxt[i] << " "; cout << endl;
        }
    }
}

signed main() {
    std::cin.tie(nullptr) -> sync_with_stdio(false);
    solve();
}