【数据结构】莫队算法

namespace MoAlgorithm {

    int n, m, BLOCK;

    struct Node {
        int l, r, id;
        bool operator<(const Node &node) const {
            if (l / BLOCK != node.l / BLOCK)
                return l < node.l;
            if ((l / BLOCK) & 1)
                return r < node.r;
            return r > node.r;
        }
    } node[200005];

    int L, R, cur, ans[200005];

    void add(int pos) {

    }

    void del(int pos) {

    }

    void Solve() {
        BLOCK = ceil(pow(n, 0.5));
        sort(node + 1, node + 1 + m);
        L = 1, R = 1, cur = 0;
        for(int i = 1; i <= m; ++i) {
            while(L > node[i].l)
                add(--L);
            while(R < node[i].r)
                add(++R);
            while(L < node[i].l)
                del(L++);
            while (R > node[i].r)
                del(R--);
            ans[node[i].id] = cur;
        }
        for(int i = 1; i <= m; ++i)
            printf("%d%c", ans[i], " \n"[i == m]);
    }

};

【数据结构】莫队算法

原文：https://www.cnblogs.com/purinliang/p/14226185.html