莫队算法学习小记

前言：

听说B组有一道莫队，我瞬间懵逼了，要让初一超了！于是赶紧去恶补算法。

莫队算法是什么？

就是可以处理离线区间查询问题的分块算法，几乎无敌。

不带修改莫队算法的实现

首先把序列以⌊n√⌋的长度分块。
把所有操作，以左端点所在的块为第一关键字，右端点为第二关键字，排个序，然后直接暴力跳就行了。

不带修改莫队算法的复杂度分析

左端点：在一个块里的时候最多跳n√格，跨两块最多2∗n√，当然，也有可能跨多块，但它最多跨n√块，一共会跳ｎ次，所以是O(n∗⌊n√⌋)
右端点：当左端点在一个块里的时候，它最多跳n次，左端点一共会在n√个块，所以复杂度是O(n∗n√)

不带修改莫队算法的代码：

裸题：【2010集训队出题】小Z的袜子

#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define sqr(a) ((a) * (a))
using namespace std;

const int N = 50005;
int n, m, sn, num[N], a[N];
ll ans[N], t[N];

struct node {
    int l, r, num;
}b[N], c[N];

bool rank(node a, node b) {
    if(num[a.l] < num[b.l]) return 1;
    if(num[a.l] > num[b.l]) return 0;
    return a.r < b.r;
}

ll gcd(ll x, ll y) {return y == 0 ? x : gcd(y, x % y);}

void ch1(ll &ans, int x, int c) {
    ans -= sqr(t[x]); t[x] += c; ans += sqr(t[x]);
}

int main() {
    freopen("len.in", "r", stdin);
    scanf("%d %d", &n, &m);
    sn = sqrt(n * 1.0);
    fo(i, 1, n) num[i] = num[i - 1] + ((i - 1) % sn == 0);
    fo(i, 1, n) scanf("%d", &a[i]);
    fo(i, 1, m) scanf("%d %d", &b[i].l, &b[i].r), b[i].num = i, c[i] = b[i];
    sort(b + 1, b + m + 1, rank);
    int l = 1, r = 0;
    fo(i, 1, m) {
        int u = b[i].num;
        ans[u] = ans[b[i - 1].num];
        fo(j, l, b[i].l - 1) ch1(ans[u], a[j], -1);
        fo(j, b[i].l, l - 1) ch1(ans[u], a[j], 1);
        fo(j, r + 1, b[i].r) ch1(ans[u], a[j], 1);
        fo(j, b[i].r + 1, r) ch1(ans[u], a[], -1);
        l = b[i].l, r = b[i].r;
    }

    fo(i, 1, m) {
        int len = c[i].r - c[i].l + 1;
        ll up = ans[i] - len, down = (ll)len * (len - 1);
        if(up == 0) printf("0/1\n"); else  {
            ll d = gcd(up, down);
            printf("%lld/%lld\n", up / d, down / d);
        }

    }
}

带修改莫队的实现：

注意修改必须是单点修改。
以n23大小来分块。
左端点所在块为第一关键字，右端点所在块为第二关键字，该查询前面有多少个修改为第三关键字，排个序（为pascal选手心累）。
然后直接扫一遍统计答案。
一些细节：我们知道这样做修改操作是要撤销的，那么可以把现在的值和要修改的值交换，下次回来撤销的时候，再交换即可，撤销操作时必须要倒着撤销。

带修改莫队的实现：

左端点：n23∗n=n53
右端点：n23∗n=n53
修改指针：n13∗n13∗n=n53
所以总复杂度是O(n53)

带修改莫队的代码：

题目：
有n个数编号从0→n-1,两种操作：
Q L R:询问编号为L→R-1的数*有多少种不同的数
M X Y：将编号为X的数改为Y
共有m个操作。
n,m<=50000
Code：

#include <cstdio>
#include <cmath>
#include <algorithm>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define fd(i, x, y) for(int i = x; i >= y; i --)
#define max(a, b) ((a) > (b) ? (a) : (b))
using namespace std;

const int N = 50005, M = 1000005;

char cc;
int sx, sc, n, m, sn, a[N], la[N], t[M], num[N], ans[N];
struct node {
    int l, r, t, num;
}b[N];
struct ch {
    int x, c;
}c[N];

bool rank(node a, node b) {
    if(num[a.l] < num[b.l]) return 1;
    if(num[a.l] > num[b.l]) return 0;
    if(num[a.r] < num[b.r]) return 1;
    if(num[a.r] > num[b.r]) return 0;
    return a.t < b.t;
}
void Init() {
    scanf("%d %d", &n, &m);
    sn = max(1, pow((long double)n, 0.66666666666));
    fo(i, 1, n) num[i] = num[i - 1] + ((i - 1) % sn == 0);
    fo(i, 1, n) scanf("%d", &a[i]);
    sx = 0, sc = 0;
    fo(i, 1, m) {
        cc = ' '; for(;cc != 'Q' && cc != 'M';cc = getchar());
        if(cc == 'Q') {
            sx ++;
            scanf("%d %d", &b[sx].l, &b[sx].r);
            b[sx].l ++;
            b[sx].t = sc; b[sx].num = sx;
        } else {
            sc ++;
            scanf("%d %d", &c[sc].x, &c[sc].c);
            c[sc].x ++;
        }
    }
    sort(b + 1, b + sx + 1, rank);
}

void ch1(int &ans, int x, int c) {
    ans -= t[x] > 0;
    t[x] += c;
    ans += t[x] > 0;
}

void ch2(int &ans, int x, int l, int r) {
    if(c[x].x >= l && c[x].x <= r) ch1(ans, a[c[x].x], -1);
    swap(a[c[x].x], c[x].c);
    if(c[x].x >= l && c[x].x <= r) ch1(ans, a[c[x].x], 1);
}

void End() {
    int l = 1, r = 0, t = 0;
    fo(i, 1, sx) {
        int u = b[i].num;
        ans[u] = ans[b[i - 1].num];
        fo(j, b[i].l, l - 1) ch1(ans[u], a[j], 1);
        fo(j, r + 1, b[i].r) ch1(ans[u], a[j], 1);

        fo(j, l, b[i].l - 1) ch1(ans[u], a[j], -1);
        fo(j, b[i].r + 1, r) ch1(ans[u], a[j], -1);

        fd(j, t, b[i].t + 1) ch2(ans[u], j, b[i].l, b[i].r);
        fo(j, t + 1, b[i].t) ch2(ans[u], j, b[i].l, b[i].r);

        l = b[i].l, r = b[i].r, t = b[i].t;
    }
    fo(i, 1, sx) printf("%d\n", ans[i]);
}

int main() {
    Init();
    End();
}

树上莫队的实现：

就是建一个数的括号序列，st[x]、en[x]分别表示x的第一次出现的位置和第二次出现的位置。
对于两点x,y,使dfn[x] <= dfn[y].
如果x是y的祖先吗，那么en[y] -> en[x]之间出现一次的点就是x->y路径上的点。
如果不是,那么en[x]->st[x]之间出现一次的点就是x->y路径上的点，除了lca，所以还要暴力处理lca。
求出每个询问需要用到哪些区间以后，按照序列上莫队的做法去完成剩下的操作即可。注意出现次数必须是1，所以我们还需开一个数组维护这个数出现了几次，一次就加，二次就减。
如果有修改，同理。
裸题是[bzoj]3757 苹果树，不用修改的.
Code：

#include<cmath>
#include <cstdio>
#include <algorithm>
#define fo(i, x, y) for(int i = x; i <= y; i ++)
#define abs(a) ((a) > 0 ? (a) : -(a))
using namespace std;

const int N = 50005, M = 100005;
int n, m, x, y, u, v, g, c[N], t[M], cha[N], num[N * 2], ans[M], st[N], en[N];
int dd, tt, dfs[N], dep[N], siz[N], fa[N], top[N], son[N], bz[N], w[N * 2];
int tot, final[N];
struct edge {
    int to, next;
}e[N * 2];
struct ask {
    int l, r, a, b, c, to;
}d[M];

void link(int x, int y) {
    e[++ tot].next = final[x], e[tot].to = y, final[x] = tot;
}

void dg1(int x) {
    dfs[x] = ++ dd;
    bz[x] = 1; siz[x] = 1;
    st[x] = ++ tt; w[tt] = x;
    for(int k = final[x]; k; k = e[k].next) {
        int y = e[k].to; if(bz[y]) continue;
        dep[y] = dep[x] + 1; fa[y] = x;
        dg1(y);
        siz[x] += siz[y];
        if(siz[y] > siz[son[x]]) son[x] = y;
    }
    en[x] = ++ tt; w[tt] = x;
    bz[x] = 0;
}
void dg2(int x) {
    bz[x] = 1;
    if(top[x] == 0) top[x] = x;
    if(son[x] != 0) top[son[x]] = top[x], dg2(son[x]);
    for(int k = final[x]; k; k = e[k].next) {
        int y = e[k].to; if(bz[y] || y == son[x]) continue;
        dg2(y);
    }
    bz[x] = 0;
}
int Lca(int x, int y) {
    while(top[x] != top[y])
        if(dep[top[x]] > dep[top[y]]) x = fa[top[x]]; else y = fa[top[y]];
    return dep[x] < dep[y] ? x : y;
}
bool rank(ask a, ask b) {
    if(num[a.l] < num[b.l]) return 1;
    if(num[a.l] > num[b.l]) return 0;
    return a.r < b.r;
}
void Init() {
    scanf("%d %d", &n, &m);
    int nd = pow(2 * n, 0.5);
    fo(i, 1, 2 * n) num[i] = num[i - 1] + ((i - 1) % nd == 0);
    fo(i, 1, n) scanf("%d", &c[i]);
    fo(i, 1, n) {
        scanf("%d %d", &x, &y);
        if(x == 0) {
            g = y; continue;
        }
        if(y == 0) {
            g = y; continue;
        }
        link(x, y);
    }
    dep[g] = 1; dg1(g);
    dg2(g);
    fo(i, 1, m) {
        scanf("%d %d %d %d", &x, &y, &u, &v);
        if(dfs[x] > dfs[y]) swap(x, y);
        int lca = Lca(x, y);
        d[i].a = u; d[i].b = v; d[i].to = i;
        if(lca == x) {
            d[i].l = en[y]; d[i].r = en[x];
        } else {
            d[i].l = en[x]; d[i].r = st[y]; d[i].c = lca;
        }
    }
    sort(d + 1, d + m + 1, rank);
}

void xiu(int &s, int x) {
    cha[x] ^= 1;
    if(cha[x]) s += ++ t[c[x]] == 1; else s -= -- t[c[x]] == 0;;
}
void End() {
    int l = 1, r = 0, la = 0;
    fo(i, 1, m) {
        while(l < d[i].l) xiu(la, w[l ++]); while(l > d[i].l) xiu(la, w[-- l]);
        while(r < d[i].r) xiu(la, w[++ r]); while(r > d[i].r) xiu(la, w[r --]);
        int u = d[i].to;
        if(d[i].c) xiu(la, d[i].c);
        ans[u] = la;
        if(d[i].a != d[i].b && t[d[i].a] && t[d[i].b]) ans[u] --;
        if(d[i].c) xiu(la, d[i].c);
    }
    fo(i, 1, m) printf("%d\n", ans[i]);
}

int main() {
    Init();
    End();
}