带修莫队板子,加上修改操作以后多了一个时间戳作为询问的第三维限制,记块大小为$B$,考虑以前两维块编号为第一二关键字,最后一维为第三关键字排序,那么前两维指针移动次数为$nB$,最后一维指针移动次数为$\displaystyle n\times \left(\frac{n}{B}\right)^2 = \frac{n^3}{B^2}$,于是取$B=n^{2/3}$时最优,复杂度为$O(n^{5/3})$
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2e6 + 10, inf = 0x3f3f3f3f;
const long long Linf = 0x3f3f3f3f3f3f3f3f;
inline int read() {
bool sym = 0; int res = 0; char ch = getchar();
while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
return sym ? -res : res;
}
struct QRY{int l, r, time, id;}qry[N];
struct MDF{int x, t;}mdf[N];
int n, m, col[N];
int l[N], r[N], bel[N], cnt[N], ans[N];
bool cmp(QRY a, QRY b) {
return bel[a.l] == bel[b.l] ? bel[a.r] == bel[b.r] ? a.time < b.time : bel[a.r] < bel[b.r] : bel[a.l] < bel[b.l];
}
bool add(int x) {return !cnt[col[x]]++;}
bool del(int x) {return !--cnt[col[x]];}
int go(int x, int now) {
int res = 0;
if (qry[x].l <= mdf[now].x && mdf[now].x <= qry[x].r) {
res = -!--cnt[col[mdf[now].x]] + !cnt[mdf[now].t]++;
}
swap(col[mdf[now].x], mdf[now].t); return res;
}
int main() {
n = read(); m = read();
for (int i = 1; i <= n; i++) col[i] = read();
int S = pow(n, 2.0 / 3.0), k = 0;
for (int i = 1; i <= n; i += S) {
l[++k] = i; r[k] = i + S - 1;
}
for (int i = 1; i <= k; i++) {
for (int j = l[i]; j <= r[i]; j++) bel[j] = i;
}
int t1 = 0, t2 = 0;
for (int i = 1; i <= m; i++) {
char opt[2]; scanf("%s", opt);
if (opt[0] == 'Q') qry[++t1] = (QRY){read(), read(), t2, t1};
if (opt[0] == 'R') mdf[++t2] = (MDF){read(), read()};
}
sort(qry + 1, qry + t1 + 1, cmp);
int l = 1, r = 0, now = 0, res = 0;
for (int i = 1; i <= t1; i++) {
while (l < qry[i].l) res -= del(l++);
while (l > qry[i].l) res += add(--l);
while (r < qry[i].r) res += add(++r);
while (r > qry[i].r) res -= del(r--);
while (now < qry[i].time) res += go(i, ++now);
while (now > qry[i].time) res += go(i, now--);
ans[qry[i].id] = res;
}
for (int i = 1; i <= t1; i++) printf("%d\n", ans[i]);
return 0;
}