介绍

上一篇莫队算法学习笔记主要写了普通莫队算法的应用，这次来写一写树上莫队和带修改莫队。
树上莫队，就是将树转化为序列，然后应用莫队算法来解决。
带修改莫队，相比于普通莫队，增加了单点修改的操作，时间复杂度由$ O(n\sqrt{n}) $ 上升到了$ O(n^{\frac{5}{3}}) $。所以，在没有其他特殊条件的情况下，对于$ n = 1e5 $次询问，一般需要2秒的处理时间。
经过实战发现，莫队算法很适合处理需要统计元素出现次数的问题，而这类问题用其他数据结构，如线段树，不太好解决~~（神犇请无视）~~。而且，莫队算法实现起来相对容易，空间消耗小。但是，莫队算法也有它的局限性，即时间复杂度偏高，且不能处理区间修改的问题。

题目1：CodeForces - 375D - Tree and Queries

题意

给一颗具有n个节点的有根树，每个节点染有一种颜色。然后有m个询问，询问的是某个节点子树的颜色数。

分析

假如我们知道了从根出发的dfs序，那么一颗子树就对应dfs序的一个区间，因此，原问题就转化成了求某个区间的颜色数，应用普通莫队即可。

代码


#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=2e5+9;
const double Eps=1e-7;

int len, cnt, in[N], out[N], c[N], nc[N], u, k, v, n, m, f[N], sum[N], ans[N];
vi G[N];

struct node {
    int l, r, k, id, block;
    node() {}
    node(int l, int r, int k, int id) {
        this->l = l;
        this->r = r;
        this->k = k;
        this->id = id;
        this->block = l / len ;
    }
    bool operator < (const node t) const {
        if(block == t.block) return r < t.r;
        return block < t.block;
    }
}q[N];

void dfs(int u, int fa) {
    in[u] = ++cnt;
    nc[cnt] = c[u];
    for(int i = 0; i < G[u].size(); i++) {
        int v = G[u][i];
        if(v == fa) continue;
        dfs(v, u);
    }
    out[u] = cnt;
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d", &n, &m)) {
        len = sqrt(n);
        for(int i = 1; i <= n; i++)
            scanf("%d", c + i);
        for(int i = 1; i < n; i++) {
            scanf("%d%d", &u, &v);
            G[u].push_back(v);
            G[v].push_back(u);
        }
        dfs(1, 0);
        for(int i = 0; i < m; i++) {
            scanf("%d%d", &u, &k);
            q[i] = node{in[u], out[u], k, i};
        }
        sort(q, q + m);
        int l = 1, r = 0;
        for(int i = 0; i < m; i++) {
            node t = q[i];
            while(r < t.r) {
                ++f[nc[++r]];
                ++sum[f[nc[r]]];
            }
            while(l > t.l) {
                ++f[nc[--l]];
                ++sum[f[nc[l]]];
            }
            while(r > t.r) {
                --sum[f[nc[r]]];
                --f[nc[r--]];
            }
            while(l < t.l) {
                --sum[f[nc[l]]];
                --f[nc[l++]];
            }
            ans[t.id] = sum[t.k];
        }
        for(int i = 0; i < m; i++)
            printf("%d\n", ans[i]);
    }

    return 0;
}

题目2：UVA - 12345 - Dynamic len

题意

给一个具有n个元素的数列，然后有m个修改或查询。查询的是某个区间的不同数子个数，修改的是某个元素的值。

分析

带修改莫队模板题，需要注意的点有：

分块大小为$ O( n^{\frac{2}{3}}) $ 。
排序时以左端点所在区块为第一关键字，右端点所在区块为第二关键字，时间戳为第三关键字。
每个时间戳都意味着状态的改变，所以需要保存更新到新状态和撤销回旧状态的相关信息。

代码


#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=1e5+9;
const double Eps=1e-7;

int len, n, m, x, y, last[N], tot, timer, a[N], l, r, ans, an[N], cnt[10*N];
bool flag[N];
char op[N];

struct node1 {
    int last, x, val;
}chg[N];

struct node {
    int l, r, id, lblock, rblock, timer;
    node() {}
    node(int l, int r, int id, int timer):l(l), r(r), id(id), timer(timer) {
        this->lblock = l / len;
        this->rblock = r / len;

    }
    bool operator < (const node t) const {
        if(lblock != t.lblock) return lblock < t.lblock;
        else if(rblock != t.rblock) return rblock < t.rblock;
        return timer < t.timer;
    }
}q[N];

void sub(int x) {
    if(cnt[a[x]] == 1)
        ans--;
    cnt[a[x]]--;
    flag[x] = 0;
}

void add(int x) {
    if(cnt[a[x]] == 0)
        ans++;
    cnt[a[x]]++;
    flag[x] = 1;
}

void modify(int x, int val) {
    if(!flag[x])
        a[x] = val;
    else {
        sub(x);
        a[x] = val;
        add(x);
    }
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d", &n, &m)) {
        len = pow(n, 2.0/3);
        for(int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            last[i] = a[i];
        }
        for(int i = 0; i < m; i++) {
            scanf("%s%d%d", op, &x, &y);
            ++x;
            if(op[0] == 'Q') {
                q[tot] = node{x, y, tot, timer};
                ++tot;
            }
            else {
                chg[++timer].last = last[x];
                chg[timer].x = x;
                chg[timer].val = last[x] = y;
            }
        }
        sort(q, q + tot);
        l = 1, r = 0, ans = 0, timer = 0;
        for(int i = 0; i < tot; i++) {
            node t = q[i];
            while(timer < q[i].timer) {
                timer++;
                modify(chg[timer].x, chg[timer].val);
            }
            while(timer > q[i].timer) {
                modify(chg[timer].x, chg[timer].last);
                timer--;
            }
            while(r < t.r)
                add(++r);
            while(l > t.l)
                add(--l);
            while(r > t.r)
                sub(r--);
            while(l < t.l)
                sub(l++);
            an[t.id] = ans;
        }
        for(int i = 0; i < tot; i++)
            printf("%d\n", an[i]);
    }

    return 0;
}

题目3：CodeForces - 940F - Machine Learning

题意

给一个具有n个元素的数列，然后有q次修改或查询。修改，即让某个元素的值改变。查询的是区间[L, R]的Mex，Mex的定义是最小的元素出现次数的次数为0的次数（不懂可以看原题）。

分析

由数学知识得，一个长度为n的数列，答案最大为$ \sqrt{2n} $，所以，假如我们维护了元素出现的次数的次数，那么我们就可以在 $ O(\sqrt{n})$得到某个区间的答案。假如没有修改操作，可以直接用普通莫队维护。但是这里有了单点的修改操作，所以我们可以考虑用带修改的莫队来实现。

代码


#include<bits/stdc++.h>
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const double PI = acos(-1.0);
const int INF=0x3f3f3f3f;
const ll LINF=0x3f3f3f3f3f3f3f3f;
const int N=2e5+9;
const double Eps=1e-7;

set<int> s;
map<int, int> ma;
int len, n, m, a[N], cnt[N], se[N], x, y, tot, timer, l, r, last[N], an[N], op, flag[N], dis, up;

struct node {
    int l, r, id, lblock, rblock, timer;
    node() {}
    node(int l, int r, int id, int timer): l(l), r(r), id(id), timer(timer) {
        this->lblock = l / len;
        this->rblock = r / len;
    }
    bool operator < (const node t) const {
        if(lblock != t.lblock) return lblock < t.lblock;
        if(rblock != t.rblock) return rblock < t.rblock;
        return timer < t.timer;
    }
}q[N];

struct node1 {
    int x, val, last;
    node1() {}
    node1(int x, int val, int last): x(x), val(val), last(last) {}
}chg[N];

void sub(int x) {
    int &t = cnt[a[x]];
    se[t]--;
    se[--t]++;
    flag[x] = 0;
}

void add(int x) {
    int &t = cnt[a[x]];
    se[t]--;
    se[++t]++;
    flag[x] = 1;
}

void modify(int x, int val) {
    if(!flag[x])
        a[x] = val;
    else {
        sub(x);
        a[x] = val;
        add(x);
    }
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    while(~scanf("%d%d", &n, &m)) {
        len = pow(n, 2.0/3);
        for(int i = 1; i <= n; i++) {
            scanf("%d", a + i);
            s.insert(a[i]);
            last[i] = a[i];
        }
        for(int i = 0; i < m; i++) {
            scanf("%d%d%d", &op, &x, &y);
            if(op == 1) {
                q[tot] = node{x, y, tot, timer};
                tot++;
            }
            else {
                timer++;
                chg[timer] = node1{x, y, last[x]};
                s.insert(y);
                last[x] = y;
            }
        }
        // 离散化
        for(auto i: s)
            ma[i] = dis++;
        for(int i = 1; i <= n; i++)
            a[i] = ma[a[i]];
        for(int i = 1; i <= timer; i++)
            chg[i].val = ma[chg[i].val], chg[i].last = ma[chg[i].last];

        // 莫队
        l = 1, r = 0, timer = 0;
        up = sqrt(2 * n);
        sort(q, q + tot);
        for(int i = 0; i < tot; i++) {
            node t = q[i];
            while(timer < t.timer) {
                timer++;
                modify(chg[timer].x, chg[timer].val);
            }
            while(timer > t.timer) {
                modify(chg[timer].x, chg[timer].last);
                timer--;
            }
            while(r < t.r) add(++r);
            while(l > t.l) add(--l);
            while(r > t.r) sub(r--);
            while(l < t.l) sub(l++);
            for(int j = 1; j <= up; j++)
                if(se[j] == 0) {
                    an[t.id] = j;
                    break;
                }
        }
        for(int i = 0; i < tot; i++) {
            printf("%d\n", an[i]);
        }
    }

    return 0;
}

hyz's blog

莫队算法学习笔记（二）

介绍

题目1：CodeForces - 375D - Tree and Queries

题意

分析

代码

题目2：UVA - 12345 - Dynamic len

题意

分析

代码

题目3：CodeForces - 940F - Machine Learning

题意

分析

代码