带修莫队（三维莫队）

 可以先看普通莫队

莫队（基础版）优雅的暴力-CSDN博客

这个数据实时更改，他。。。没法离线！

但是，真的没有办法吗，，，带修莫队可以

带修改的莫队算法

在传统莫队的基础上增加了 "时间" 维度。每个查询不仅有左右端点(l, r)，还有一个时间戳t，表示在处理这个查询时，允许使用前t次修改操作的结果。 

核心，记录并维护时间节点产生的数据变化，然后再和二维融合 

 

 分块变种，加了时间维度

struct Query {int l, r, t, id;bool operator<(const Query& rhs) const {if (l/block_size != rhs.l/block_size) return l < rhs.l;if (r/block_size != rhs.r/block_size) return r < rhs.r;//右不同return t < rhs.t;//同再判时间}
} q[MAXN];

可见，我们就是再一个空间上，又双去找最佳路径了 

ps：分块大小选择为n^(2/3)时，时间复杂度为O(n^(5/3))

额外的：

struct Modify {int pos, val;  // 记录修改位置和修改后的值
} c[MAXN];

维护时间变化的修改 

inline void update(int l, int r, int& time, int target) {// 时间前进：应用更多修改while (time < target) {time++;int p = c[time].pos;  // 获取修改位置if (l <= p && p <= r) {  // 如果修改位置在当前区间内del(a[p]);          // 移除旧值add(c[time].val);   // 添加新值}swap(a[p], c[time].val);  // 实际应用修改（无论是否在区间内）}// 时间回退：撤销后续修改while (time > target) {int p = c[time].pos;if (l <= p && p <= r) {del(a[p]);           // 移除当前值（实际是未来修改后的值）add(c[time].val);    // 添加旧值（修改前的值）}swap(a[p], c[time].val);  // 撤销修改，回到过去状态time--;}
}

 

 

 

完整代码 

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

const int MAXN = 2e5 + 5;
const int MAXM = 1e6 + 5;

int n, m, a[MAXN], cnt[MAXM], ans[MAXN];
int now, block_size;

struct Query {
    int l, r, t, id;
    bool operator<(const Query& rhs) const {
        if (l/block_size != rhs.l/block_size) return l < rhs.l;
        if (r/block_size != rhs.r/block_size) return r < rhs.r;
        return t < rhs.t;//时间
    }
} q[MAXN];

struct Modify {
    int pos, val;
} c[MAXN];

inline void add(int x) {
    now += !cnt[x]++;
}

inline void del(int x) {
    now -= !--cnt[x];
}

inline void update(int l, int r, int& time, int target) {
    while (time < target) {
        time++;
        int p = c[time].pos;
        if (l <= p && p <= r) {
            del(a[p]);
            add(c[time].val);
        }
        swap(a[p], c[time].val);
    }
    while (time > target) {
        int p = c[time].pos;
        if (l <= p && p <= r) {
            del(a[p]);
            add(c[time].val);
        }
        swap(a[p], c[time].val);
        time--;
    }
}//维护时间

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n >> m;
    block_size = pow(n, 0.666);//三维区块大小2/3
    
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    int cnt_q = 0, cnt_c = 0;
    for (int i = 0; i < m; i++) {
        char op; int x, y;
        cin >> op >> x >> y;
        if (op == 'Q') {
            q[++cnt_q] = {x, y, cnt_c, cnt_q};
        } else {
            c[++cnt_c] = {x, y};
        }
    }
    
    sort(q + 1, q + cnt_q + 1);
    
    int l = 1, r = 0, t = 0;
    for (int i = 1; i <= cnt_q; i++) {
        while (l > q[i].l) add(a[--l]);
        while (r < q[i].r) add(a[++r]);
        while (l < q[i].l) del(a[l++]);
        while (r > q[i].r) del(a[r--]);
        update(q[i].l, q[i].r, t, q[i].t);//更新时间引起的变化
        ans[q[i].id] = now;
    }
    
    for (int i = 1; i <= cnt_q; i++) cout << ans[i] << '\n';
    
    return 0;
}