莫队

• 普通莫队算法

给出一个序列，要求每次查询L, R中满足某些条件的数字，输出每次查询的结果

正常操作下需要进行$O(n^2)$ ，但是使用莫队可以实现 $O(nsqrt(n))$ 查询所有操作；

莫队主要在于预先处理 查询操作，用 l 和 r 两个指针找到当前窗口，每次移动指针使得时间复杂度降低。

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
struct Query {
    int l, r, id;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    vector<Query> que(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        que[i] = { l, r, i };
    }

    int len = sqrt(n);
    ranges::sort(que, [&](const Query& p, const Query& q) {
        int as = (p.l - 1) / len + 1;
        int bs = (q.l - 1) / len + 1;
        if (as != bs) return as < bs;
        else return p.r < q.r;
    });

    int cur = 0;
    vector<int> cnt(1e6);
    auto add = [&](int pos) -> void {
        cnt[a[pos]]++;
        if (cnt[a[pos]] == 1) {
            cur++;
        }
    };

    auto del = [&](int pos) -> void {
        cnt[a[pos]]--;
        if (cnt[a[pos]] == 0) {
            cur--;
        }
    };

    int nowr = 0, nowl = 1;

    vector<int> ans(q);
    for (auto &x : que) {
        auto [l, r, id] = x;

        while (nowr < r) {
            nowr++;
            add(nowr);
        }
        while (nowr > r) {
            del(nowr);
            nowr--;
        }
        while (nowl < l) {
            del(nowl);
            nowl++;
            
        }
        while (nowl > l) {
            nowl--;
            add(nowl);
        }

        if (cur == r - l + 1) {
            ans[id] = 1;
        } else {
            ans[id] = 0;
        }
    }

    for (int i = 0; i < q; i++) {
        if (ans[i]) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
    return 0;
}

• 莫队不止可以进行静态询问，还可以支持修改查询，需要在原来基础上再加上的一个维度，记录修改的次数t，每次移动的时候再将其移动到对应的版本。(P1930)

#include<bits/stdc++.h>
using namespace std;
using i64 = long long;
struct Query {
    int l, r, t, id;
};

struct Modify {
    int pos, p, v;
};
const int SIZ = 1e6 + 7;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<int> a0(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a0[i];
    }

    vector<int> a(a0);
    
    vector<Query> que;
    vector<Modify> mo;
    int curt = 0;

    for (int i = 0; i < m; i++) {
        char u;
        int l, r;
        cin >> u >> l >> r;
        if (u == 'Q') {
            que.emplace_back(l, r, curt, (int)que.size());
        } else {
            mo.emplace_back(l, a0[l], r);
            a0[l] = r;
            curt++;
        }
    }

    int len = pow(n, 2.0 / 3); // 块长， 一般取（m^1/3）或者 (n^2/3);

    ranges::sort(que, [&](const Query& p, const Query& q) {
        int as = (p.l - 1) / len + 1, bs = (q.l - 1) / len + 1;
        if (as != bs) return as < bs;
        int ra = (p.r - 1) / len + 1, rb = (q.r - 1) / len + 1;
        if (ra != rb) return ra < rb;
        return p.t < q.t;
    });

    vector<int> cnt(SIZ);
    int cur = 0;
    int curl = 1, curr = 0;
    curt = 0;
    auto add = [&](int pos) -> void {
        cnt[a[pos]]++;
        if (cnt[a[pos]] == 1) {
            cur++;
        }
    };

    auto del = [&](int pos) -> void {
        cnt[a[pos]]--;
        if (cnt[a[pos]] == 0) {
            cur--;
        }
    };

    auto apply = [&](int t) -> void {
        int pos = mo[t].pos;
        if (curl <= pos && pos <= curr) {
            del(pos);
        }
        a[pos] = mo[t].v;
        if (curl <= pos && pos <= curr) {
            add(pos);
        }
    };

    auto roll = [&](int t) -> void {
        int pos = mo[t].pos;
        if (curl <= pos && pos <= curr) {
            del(pos);
        }
        a[pos] = mo[t].p;
        if (curl <= pos && pos <= curr) {
            add(pos);
        }
    };

    vector<int> ans(que.size());
    for (auto q : que) {
        auto [l, r, t, id] = q;

        while (curt < t) {
            apply(curt);
            curt++;
        }
        while (curt > t) {
            curt--;
            roll(curt);
        }

        while (curr < r) {
            curr++;
            add(curr);
        }
        while (curr > r) {
            del(curr);
            curr--;
        }
        while (curl < l) {
            del(curl);
            curl++;
        }
        while (curl > l) {
            curl--;
            add(curl);
        }
        ans[id] = cur;
    }

    for (auto x : ans) {
        cout << x << '\n';
    }
    return 0;
}