莫队算法学习笔记

我相信莫队本人应该没有想到他的莫队算法不仅可以做到支持修改而且还可以上树甚至在树上都可以支持修改吧（笑。

传统的莫队是将询问储存为询问的左端点和右端点，然后对序列以 $\sqrt n$ 为长度分块，以左端点所在块为第一关键字，右端点为第二关键字排序然后暴力，这样的做法的时间复杂度是 $O(n \sqrt n)$ 即 $O(n ^ {\frac 3 2})$ 的。

反正就是个排序再暴力有啥子好讲的，复杂度证明这种事管他呢（其实不带修改的莫队我还是可以证一下的。

好啦以上是复习！

如果需要支持单点修改该怎么办呢？

解决方案是，对于每一个询问，不仅记录询问的区间端点，而且记录下在它之前离它最近的修改操作。对于每一个修改操作，记录下它修改的位置，以及修改前后的值。

就像这样。

struct Query {
    int l, r;
    Change *x;
    int *ans;
} querys[N + 1], *queryEnd;
struct Change {
    int pos, newVal, oldVal;
} changes[N + 1], *changeEnd;

以 $n ^ {\frac 2 3}$ 为大小分块，排序时按照左端点所在块为第一关键字，右端点所在块为第二关键字，离它最近的修改操作的位置为第三关键字排序，然后暴力。

处理修改操作时维护一个指针，每次记录此次操作之后修改指针停留的位置，对于某个询问，如果当前修改指针在离它最近的指针之前，就正着改过去，如果在之后，就倒着改回去。正确性显然。记得处理能影响到当前区间的位置就好了。

这样做的时间复杂度被证明是 $O(n ^ {\frac 5 3})$ 的。

这里是带修改莫队的一道例题，Uva12345的代码。（此题同 BZOJ2120，BZOJ2453.

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
const int N = 50000;
const int MAX = 1000000;
struct Query;
struct Change;
struct Query {
    int l, r;
    Change *x;
    int *ans;
} querys[N + 1], *queryEnd;
struct Change {
    int pos, newVal, oldVal;
} changes[N + 1], *changeEnd;
int n, m;
int block[N + 1], last[N + 1];
int res, ans[N + 1];
bool affected[N + 1];
int buc[MAX + 1], a[N + 1];
int l, r;
Change *now;
int blockSize;
inline bool comp(const Query &x, const Query &y) {
    return block[x.l] < block[y.l] ||
           block[x.l] == block[y.l] && block[x.r] < block[y.r] ||
           block[x.l] == block[y.l] && block[x.r] == block[y.r] && x.x < y.x;
}
inline void update(int pos) {
    if (affected[pos]) {
        if (!--buc[a[pos]]) res--;
    } else {
        if (!buc[a[pos]]++) res++;
    }
    affected[pos] ^= 1;
}
inline void modify(int pos, int val) {
    if (affected[pos]) {
        update(pos);
        a[pos] = val;
        update(pos);
    } else a[pos] = val;
}
int main() {
    queryEnd = querys;
    changeEnd = changes;
    scanf("%d %d", &n, &m);
    blockSize = 1500;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        block[i] = i / blockSize;
        last[i] = a[i];
    }
    for (int i = 1; i <= m; i++) {
        char s[10];
        int x, y;
        scanf("%s %d %d", s, &x, &y);
        if (s[0] == 'Q') {
            x++;
            queryEnd++;
            queryEnd->l = x;
            queryEnd->r = y;
            queryEnd->x = changeEnd;
            queryEnd->ans = &ans[queryEnd - querys];
        } else {
            x++;
            changeEnd++;
            changeEnd->pos = x;
            changeEnd->newVal = y;
            changeEnd->oldVal = last[x];
            last[x] = y;
        }
    }
    std::sort(querys + 1, queryEnd + 1, comp);
    l = 1;
    r = 0;
    now = changes;
    for (Query *v = querys + 1; v != queryEnd + 1; v++) {
        if (now == v->x) {}
        else if (now < v->x) {
            for (Change *p = now + 1; p != v->x + 1; p++) modify(p->pos, p->newVal);
        } else {
            for (Change *p = now; p != v->x + 1 - 1; p--) modify(p->pos, p->oldVal);
        }
        if (l == v->l) {}
        if (l < v->l) for (int i = l; i <= v->l - 1; i++) update(i);
        else for (int i = v->l; i <= l - 1; i++) update(i);
        if (r == v->r) {}
        if (r < v->r) for (int i = r + 1; i <= v->r; i++) update(i);
        else for (int i = v->r + 1; i <= r; i++) update(i);
        l = v->l;
        r = v->r;
        now = v->x;
        *v->ans = res;
    }
    for (int i = 1; i <= queryEnd - querys; i++) printf("%d\n", ans[i]);
    return 0;
}