总览

用来处理一类可以离线处理的多区间询问问题。
本质是安排区间的处理顺序使程序优化到一个较优的复杂度。

本质骗分算法
有不少以其为正解的题目（大概

教程建议看 @大米饼 的博客园：https://www.cnblogs.com/Paul-Guderian/p/6933799.html
对没错，就是百度第一篇。

然后就是莫队本人推荐的那个知乎专栏：https://zhuanlan.zhihu.com/p/25017840

看完这两篇就差不多了。

标题说的三道例题也全都是大米饼给的例题。
他的代码比较精简，有许多可以借鉴的地方。
但第三题可能过于精简了，以至于我看不懂。

于是只讲下第三题吧。

Haruna’s Breakfast

树上带修莫队 + 分块。
根据大米饼和第二篇文章的说法，树上的莫队有两种做法：

1. 括号序列处理（什么是括号序列？百度哇）
2. 树上分块

我不会 2，就用第一种方法来处理。
怎么处理呢？参考第二篇文章的 0x02 章节。
为了更好的阅读体验我就不搬过来了。

另外一点，就是求 mex 的问题。
这里有关于 mex 的简介，就是出自著作《Game Theory》的定义：

In mathematics, the mex of a subset of a well-ordered set is the smallest value from the whole set that does not belong to the subset. That is, it is the minimum value of the complement set. The name "mex" is shorthand for "minimum excluded" value.

看得懂吧？
看不懂也没关系，题目里不是讲了这个东西嘛。

我们采用分块来处理 mex。$O(1)$ 进行修改，$O(\sqrt{n})$ 进行查询。
我们首先要了解的一点就是：我们可以忽略所有 $>n$ 的数。因为取不到那里去。请自行思考。

于是考虑所有 $< n$ 的数就行。分 $\sqrt{n}$ 块，每块统计出现的数的种类数。如果这个种类数 = 块的大小，则可以确定这个块已经被填满了。找到的第一个没有被填满的块，mex 就在这个区间里。

原理就很清楚了。

LCA 我用了树链剖分来处理。至于为什么要用 namespace 封装，我想我打算养成这个习惯，所以试试。

顺便一提，复杂度是 $O(2n^{\frac{5}{3}}+n\sqrt{n})$, 应该是炸了的，但是没有。由此可见复杂度挺玄学的。

Code

// Code by ajcxsu
// Problem: BZOJ4129 Haruna's breakfast

#include<bits/stdc++.h>
using namespace std;

const int N=5e4+10, M=1e5+10;
int h[N],to[M],nexp[M],p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
int seq[2*N],sp; // 括号序列
int sl[N],sr[N]; // 每个点在括号序列中的出现位置
int del[N],cnt[N]; // 美味值，计数
int now[N];
int n,m;

struct Query { int l,r,t,id,ex; } q[N];
struct Change { int x,d,old; } c[N];
int pq,pc;
int be[N*2],unit; // 分块
bool cmp(const Query &a, const Query &b) { return be[a.l]==be[b.l]? (be[a.r]==be[b.r]?a.t<b.t:a.r<b.r) :a.l<b.l; }
int ans[N]; // 答案序列

struct Block {
    int n,pos[N],m,block;
    int l[350],r[350];
    void ini() {
        block=sqrt(n); m=(n-1)/block+1; // m=ceil(n/block)
        for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1;
        for(int i=1;i<=m;i++) l[i]=(i-1)*block+1, r[i]=i*block;
        l[1]=0;
        pos[0]=1;
        r[m]=n;
    }
    int cnt[N],sum[350];
    inline void add(int v) { if(v<=n) sum[pos[v]]+=(++cnt[v])==1; }
    inline void del(int v) { if(v<=n) sum[pos[v]]-=(cnt[v]--)==1; }
    int mex() {
        for(int i=1;i<=m;i++) if(sum[i]!=r[i]-l[i]+1)
            for(int j=l[i];j<=r[i];j++) if(!cnt[j]) return j;
        return -1;
    }
} bl;


void revise(int x) {
    if(!cnt[x]) bl.add(del[x]); // 如果出现过0/2次，插入
    else bl.del(del[x]); // 否则删除
    cnt[x]^=1; // 不能加减，只能异或（加减出现次数可能会出-1、-2，这在这里面判断就麻烦一些）
}
void going(int x, int d) {
    if(cnt[x]) { bl.del(del[x]), bl.add(d); }
    del[x]=d;
}

/* 树剖求LCA */
namespace LCA {
    int dep[N],son[N],siz[N],fa[N];
    int top[N],idx;
    void dfs1(int x,int k) {
        dep[x]=k, siz[x]=1;
        seq[++sp]=x, be[sp]=sp/unit+1; // 顺便处理一下括号序列
        sl[x]=sp;
        for(int u=h[x];u;u=nexp[u])
            if(!dep[to[u]]) {
                fa[to[u]]=x, dfs1(to[u], k+1);
                siz[x]+=siz[to[u]];
                son[x]=siz[to[u]]>siz[son[x]]? to[u]: son[x];
            }
        seq[++sp]=x, be[sp]=sp/unit+1;
        sr[x]=sp;
    }
    void dfs2(int x,int t) {
        top[x]=t;
        if(son[x]) dfs2(son[x],t);
        for(int u=h[x];u;u=nexp[u])
            if(!top[to[u]]) dfs2(to[u],to[u]);
    }
    int lca(int s,int t) {
        while(top[s]!=top[t]) {
            if(dep[top[s]]<dep[top[t]]) swap(s,t);
            s=fa[top[s]];
        }
        if(dep[s]>dep[t]) return t;
        else return s;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin>>n>>m;
    bl.n=n, bl.ini();
    unit=pow(2*n,2.0/3.0);

    for(int i=1;i<=n;i++) cin>>del[i], now[i]=del[i];
    /* 输入 */
    for(int i=0,u,v;i<n-1;i++) cin>>u>>v, ins(u,v), ins(v,u);
    LCA::dfs1(1,1), LCA::dfs2(1,1); // LCA init
    /* 处理输入序列 */
    for(int i=1,a,u,v,lca;i<=m;i++) {
        cin>>a>>u>>v;
        if(a==0) { c[++pc].x=u, c[pc].d=v, c[pc].old=now[u], now[u]=v; }
        else {
            ++pq;
            q[pq].id=pq, q[pq].t=pc;
            lca=LCA::lca(u,v);
            if(lca==u || lca==v) {
                if(sr[u]>sr[v]) swap(u,v);
                q[pq].l=sr[u], q[pq].r=sr[v], q[pq].ex=-1;
            }
            else {
                if(sl[u]>sr[v]) swap(u,v);
                q[pq].l=sl[u]+1, q[pq].r=sr[v]-1, q[pq].ex=lca;
            }
        }
    }
    sort(q+1,q+1+pq,cmp);
    int l=1,r=0,t=0;
    for(int i=1;i<=pq;i++) {
        while(t<q[i].t) going(c[t+1].x, c[t+1].d), t++;
        while(t>q[i].t) going(c[t].x, c[t].old), t--;

        while(l<q[i].l) revise(seq[l]), l++;
        while(l>q[i].l) revise(seq[l-1]), l--;
        while(r<q[i].r) revise(seq[r+1]), r++;
        while(r>q[i].r) revise(seq[r]), r--;

        if(q[i].ex!=-1) bl.add(del[q[i].ex]);
        ans[q[i].id]=bl.mex();
        if(q[i].ex!=-1) bl.del(del[q[i].ex]);
    }
    for(int i=1;i<=pq;i++) cout<<ans[i]<<endl;
    return 0;
}

【WC2013】糖果公园

upd: 2018-10-26

好像也是一道比较经典的例题。
为了复习树上莫队就把这题写了一下，发现以下几个值得注意的地方：

• 在going函数中，判断贡献是否更改，是判断更改的元素是否处在你当前的统计范围之内（ $vis=1$ ），而不是其它的因素。其它的因素可能导致不在你统计范围内的点被统计。
• 注意，括号序列的长度是 $2n$，所以无论是设置块大小还是统计所属块都得注意。
• 块的大小应是 $(2n)^\frac{2}{3}$ 。

Code

// Code by ajcxsu
// Problem: candy park

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
typedef long long ll;
using namespace std;

template<typename T> inline void gn (T &x) {
    char ch=getchar(), pl=0; x=0;
    while(ch<'0' || ch>'9') {
        if(ch==-1) exit(0);
        pl=ch=='-', ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}

const int N=2e6+10, M=2e6+10;
int h[N], to[M], nexp[M], p=1;
inline void ins(int a, int b) { nexp[p]=h[a], h[a]=p, to[p]=b, p++; }
int seq[N], sl[N], sr[N], sp;
namespace LCA {
    int dfn[N], siz[N], fa[N], top[N], dep[N], son[N], idx;
    void dfs1(int x, int k) {
        dep[x]=k, siz[x]=1;
        for(int u=h[x];u;u=nexp[u])
            if(!dep[to[u]]) {
                dfs1(to[u], k+1), fa[to[u]]=x, siz[x]+=siz[to[u]];
                if(siz[to[u]]>siz[son[x]]) son[x]=to[u];
            }
    }
    void dfs2(int x, int t) {
        dfn[x]=++idx, top[x]=t, seq[++sp]=x, sl[x]=sp;
        if(son[x]) dfs2(son[x], t);
        for(int u=h[x];u;u=nexp[u])
            if(!dfn[to[u]]) dfs2(to[u], to[u]);
        seq[++sp]=x, sr[x]=sp;
    }
    void ini() { dfs1(1, 1), dfs2(1, 1); }
    int work(int x, int y) {
        while(top[x]!=top[y]) {
            if(dep[top[x]]<dep[top[y]]) swap(x, y);
            x=fa[top[x]];
        }
        return dep[x]>dep[y]?y:x; 
    }
}

struct Query { int l, r, t, id, ex; } qu[N];
int blo[N];
bool cmp(const Query &a, const Query &b) {
    return blo[a.l]==blo[b.l]?(blo[a.r]==blo[b.r]?a.t<b.t:a.r<b.r):a.l<b.l; 
}
struct Change { int x, y, old; } c[N];
int col[N];
ll v[N], w[N];
int cnt[N], nv[N];
char vis[N];
ll ans;
ll tot[N];
void going(int x, int y) {
    if(vis[x]) { //!!
        ans-=v[col[x]]*w[cnt[col[x]]--];
        ans+=v[y]*w[++cnt[y]];
    }
    col[x]=y;
}
void revise(int x) {
    x=seq[x];
    if(vis[x]) {
        vis[x]=0;
        ans-=v[col[x]]*w[cnt[col[x]]--];
    }
    else {
        vis[x]=1;
        ans+=v[col[x]]*w[++cnt[col[x]]];
    }
}

int main() {
    int n, m, q, unit;
    gn(n), gn(m), gn(q), unit=pow(n<<1, 2.0/3.0); // !!
    for(int i=1;i<=m;i++) gn(v[i]);
    for(int i=1;i<=n;i++) gn(w[i]);
    int u, v;
    for(int i=0;i<n-1;i++) gn(u), gn(v), ins(u, v), ins(v, u);
    for(int i=1;i<=n;i++) gn(col[i]), nv[i]=col[i];
    LCA::ini();
    int x;
    int cp=0, qp=0, lca;
    int l=1, r=0, t=0;
    for(int i=1;i<=(n*2);i++) blo[i]=i/unit; // !!
    for(int i=0;i<q;i++) {
        gn(x), gn(u), gn(v);
        if(!x) c[++cp]={u, v, nv[u]}, nv[u]=v;
        else {
            ++qp;
            lca=LCA::work(u, v);
            if(lca==u || lca==v) {
                if(sr[u]>sr[v]) swap(u, v);
                qu[qp]={sr[u], sr[v], cp, qp, -1};
            }
            else {
                if(sl[u]>sr[v]) swap(u, v);
                qu[qp]={sl[u]+1, sr[v]-1, cp, qp, lca};
            }
        }
    }
    sort(qu+1, qu+1+qp, cmp);
    for(int i=1;i<=qp;i++) {
        while(t<qu[i].t) going(c[t+1].x, c[t+1].y), t++;
        while(t>qu[i].t) going(c[t].x, c[t].old), t--;
        
        while(l<qu[i].l) revise(l), l++;
        while(l>qu[i].l) revise(l-1), l--;
        while(r<qu[i].r) revise(r+1), r++;
        while(r>qu[i].r) revise(r), r--;

        if(qu[i].ex!=-1) ans+=::v[col[qu[i].ex]]*w[cnt[col[qu[i].ex]]+1];
        tot[qu[i].id]=ans;
        if(qu[i].ex!=-1) ans-=::v[col[qu[i].ex]]*w[cnt[col[qu[i].ex]]+1];
    }
    for(int i=1;i<=qp;i++) printf("%lld\n", tot[i]);
    return 0;
}