@KirinBill 2018-02-26T21:53:47.000000Z 字数 21523 阅读 1433

莫队算法学习笔记

分块

目录

莫队算法学习笔记

算法思想

练习

普通莫队

带修改莫队

树上莫队

子树查询

链上查询

带修改

算法思想

考虑一类询问序列区间信息的问题，如果我们知道了 $[l,r]$ 的答案，并能够快速的由此推出 $[l \pm 1,r \pm 1]$ 的答案，那么就可以使用莫队算法进行离线处理了；
虽然这种问题可以将区间抽象成平面上一个点，从这个询问更新到另一个的代价是曼哈顿距离，我们求出曼哈顿距离最小生成树后从直径一端遍历到另一端就是最优回答顺序，但代码比较复杂，而相对暴力但简单的莫队是很好的选择，复杂度也没有慢太多；
莫队算法的思想是用两个指针维护当前处理的区间的左右端点，每次处理下一个询问时，暴力移动指针，由于我们已经要求推出 $[l \pm 1,r \pm 1]$ 的答案的速度很快，那么整个算法的瓶颈就在于指针的移动次数；
考虑分块，将询问升序排序，第一关键字为左端点所在块的标号，第二关键字为右端点位置，设块的大小为 $S$ ，区间长度为 $n$ ，询问次数与 $n$ 同阶（通常是这样的，如果不是的话需要具体分析块的大小，分块这个本来就是要这样，具体分析一下才能取到最优）；
那么指针的移动有以下三类：
- $r$ 指针：
  1. 当 $l$ 在一个块内移动的时，由于将询问按右端点递增排了，所以最坏移动 $n$ 次。而共有 $\frac{n}{S}$ 个块，也就出现这么多次；
  2. 当 $l$ 跨块时， $r$ 最坏从 $n$ 移动回 $1$ ，为 $n$ 次。 $l$ 最多从第一个块跨到最后一个，所以这种情况最多出现 $\frac{n}{S}$ 次。
  综上， $r$ 的移动次数为 $O(\frac{n^2}{S})$ 。
- $l$ 指针：
  1. 当 $l$ 在一个块内移动的时，每次最多从块的一端移动到另一端，也就是移动 $S$ 次。而共有 $n$ 个询问，忽略跨块的话也就出现这么多次；
  2. 当 $l$ 跨块时，最坏从上一个块的最左端移动到这一个块的最右端，移动次数仍是 $O(S)$ 次。而共有 $\frac{n}{S}$ 个块，也就出现这么多次；
  综上， $l$ 的移动次数为 $O(nS+\frac{n^2}{S})$ 。
注意到瓶颈在 $l$ 的移动，考虑均值不等式，那么当 $nS=\frac{n^2}{S}$ ，也就是 $S=\sqrt{n}$ 时复杂度最优；
所以如果设每次更新答案的复杂度为 $O(x)$ ，那么普通莫队算法的复杂度通常是 $O(x \times n\sqrt{n})$

练习

普通莫队

普通莫队的话就是像上面说的那样操作就行了，比较简单；
通常只需要考虑如何转化问题，能够快速更新答案。

1.[BZOJ 3781] 小B的询问
- 第一道题，说的详细一点；
- 先用一个数组记录序列上的每个点是否加入答案，每次移动指针就调用add函数，如果当前点加入答案了就删掉，不然就加进去（这是为了兼容后面的树上莫队）；
- 用一个桶记录当前区间中每种颜色的出现次数，之后正常计算就行了；
- 每次修改和查询都是 $O(1)$ 计算，所以复杂度为 $O(n \sqrt{n})$ 。

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
using std::sqrt;
using std::sort;
const int MAXN=50005,MAXM=MAXN,MAXK=MAXN;
int m;
int a[MAXN],buc[MAXK];
long long ans[MAXM];
bool use[MAXN];
struct query{
    int lp,rp,l_blk;
    long long *ans;
    static bool cmp(const query &a,const query &b){
        return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
    }
}qry[MAXM];
inline long long sqr(register long long x){return x*x;}
inline void ist(int u){
    ans[0]-=sqr(buc[a[u]]);
    ++buc[a[u]];
    ans[0]+=sqr(buc[a[u]]);
}
inline void del(int u){
    ans[0]-=sqr(buc[a[u]]);
    --buc[a[u]];
    ans[0]+=sqr(buc[a[u]]);
}
inline void add(int u){
    if(use[u]) del(u),use[u]=false;
    else ist(u),use[u]=true;
}
inline void MoCpt(){
    sort(qry+1,qry+m+1,query::cmp);
    for(int i=1,l=1,r=0;i<=m;++i){
        while(l<qry[i].lp) add(l++);
        while(l>qry[i].lp) add(--l);
        while(r<qry[i].rp) add(++r);
        while(r>qry[i].rp) add(r--);
        *qry[i].ans=ans[0];
    }
}
int main(){
    int n,k;
    scanf("%d%d%d",&n,&m,&k);
    int BLK_SZ=sqrt(n)+0.5;
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&qry[i].lp,&qry[i].rp);
        qry[i].l_blk=qry[i].lp/BLK_SZ;
        qry[i].ans=&ans[i];
    }
    MoCpt();
    for(int i=1;i<=m;++i)
        printf("%lld\n",ans[i]);
    return 0;
}

2.[集训队互测 2009] 小Z的袜子

变形一下式子：

$\frac{\sum_{i=1}^{max\_col}\text{C}_{cnt_i}^2}{\text{C}_{cnt}^2}$
那么我们只需要求出来分子就可以了，其实就是每次更改 $\text{C}_{cnt_i}^2$ ；
复杂度仍是 $O(n \sqrt{n})$

代码：

#include <cstdio>
#include <algorithm>
#include <cmath>
using std::sort;
using std::sqrt;
const int MAXN=50005;
int m;
long long ans;
int cnt[MAXN],col[MAXN];
long long up[MAXN],dwn[MAXN];
bool use[MAXN];
struct query{
    int lp,rp,l_blk;
    long long *up;
    static bool cmp(const query &a,const query &b){
        return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
    }
}qry[MAXN];
template<typename type>
inline type gcd(register type a,register type b){
    register type r;
    while(b){r=a%b,a=b,b=r;}
    return a;
}
inline void ist(int u){
    ans-=(long long)cnt[col[u]]*(cnt[col[u]]-1)>>1;
    ++cnt[col[u]];
    ans+=(long long)cnt[col[u]]*(cnt[col[u]]-1)>>1;
}
inline void del(int u){
    ans-=(long long)cnt[col[u]]*(cnt[col[u]]-1)>>1;
    --cnt[col[u]];
    ans+=(long long)cnt[col[u]]*(cnt[col[u]]-1)>>1;
}
inline void add(int u){
    if(use[u]) del(u),use[u]=false;
    else ist(u),use[u]=true;
}
inline void MoCpt(){
    sort(qry+1,qry+m+1,query::cmp);
    for(int i=1,l=1,r=0;i<=m;++i){
        while(l<qry[i].lp) add(l++);
        while(l>qry[i].lp) add(--l);
        while(r<qry[i].rp) add(++r);
        while(r>qry[i].rp) add(r--);
        *qry[i].up=ans;
    }
}
int main(){
    int n;
    scanf("%d%d",&n,&m);
    int BLK_SZ=sqrt(n)+0.5;
    for(int i=1;i<=n;++i)
        scanf("%d",&col[i]);
    for(int i=1;i<=m;++i){
        scanf("%d%d",&qry[i].lp,&qry[i].rp);
        dwn[i]=(long long)(qry[i].rp-qry[i].lp+1)*(qry[i].rp-qry[i].lp)>>1;
        qry[i].l_blk=qry[i].lp/BLK_SZ;
        qry[i].up=&up[i];
    }
    MoCpt();
    long long gcd;
    for(int i=1;i<=m;++i){
        gcd=::gcd(up[i],dwn[i]);
        printf("%lld/%lld\n",up[i]/gcd,dwn[i]/gcd);
    }
    return 0;
}

3.[BZOJ 3289] Mato的文件管理

题目就是让求区间中的逆序对数，很容易想到用树状数组维护；
现在考虑怎么更新答案：
1. 移动 $l$ 指针：那么影响的个数就是 $\sum_{i=l+1}^r[a_i<a_l]$ ；
2. 移动 $r$ 指针：那么影响的个数就是 $\sum_{i=l}^{r-1}[a_i>a_r]$ 。
每次更新是 $O(\log{n})$ 的，所以复杂度是 $O(n \sqrt{n}\log{n})$

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using std::sqrt;
using std::sort;
using std::unique;
using std::lower_bound;
const int MAXN=50005,MAXQ=MAXN;
int n,q,ta_n;
int a[MAXN];
long long ans[MAXQ];
struct query{
    int lp,rp,l_blk;
    long long *ans;
    static bool cmp(const query &a,const query &b){
        return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
    }
}qry[MAXQ];
class BIT{
    private:
        long long c[MAXN];
        int lowbit(register int x){return x&-x;}
        long long qry(int r){
            long long ret=0;
            for(;r;r-=lowbit(r))
                ret+=c[r];
            return ret;
        }
    public:
        void add(int l,int x){
            for(;l<=ta_n;l+=lowbit(l))
                c[l]+=x;
        }
        long long qry(int l,int r){return qry(r)-qry(l-1);}
}ta;
inline void MoCpt(){
    sort(qry+1,qry+q+1,query::cmp);
    for(int i=1,l=1,r=0;i<=q;++i){
        while(l<qry[i].lp){
            ans[0]-=ta.qry(1,a[l]-1);
            ta.add(a[l],-1);
            ++l;
        }
        while(l>qry[i].lp){
            --l;
            ans[0]+=ta.qry(1,a[l]-1);
            ta.add(a[l],1);
        }
        while(r<qry[i].rp){
            ++r;
            ans[0]+=ta.qry(a[r]+1,ta_n);
            ta.add(a[r],1);
        }
        while(r>qry[i].rp){
            ans[0]-=ta.qry(a[r]+1,ta_n);
            ta.add(a[r],-1);
            --r;
        }
        *qry[i].ans=ans[0];
    }
}
inline void decrete(){
    static int tmp[MAXN];
    memcpy(tmp,a,sizeof(tmp));
    sort(tmp+1,tmp+n+1);
    ta_n=unique(tmp+1,tmp+n+1)-tmp-1;
    for(int i=1;i<=n;++i)
        a[i]=lower_bound(tmp+1,tmp+n+1,a[i])-tmp;
}
int main(){
    scanf("%d",&n);
    int BLK_SZ=sqrt(n)+0.5;
    for(int i=1;i<=n;++i)
        scanf("%d",&a[i]);
    decrete();
    scanf("%d",&q);
    for(int i=1;i<=q;++i){
        scanf("%d%d",&qry[i].lp,&qry[i].rp);
        qry[i].l_blk=qry[i].lp/BLK_SZ;
        qry[i].ans=&ans[i];
    }
    MoCpt();
    for(int i=1;i<=q;++i)
        printf("%lld\n",ans[i]);
    return 0;
}

4.[AHOI 2013] 作业

题目是求当前区间值域在 $[a,b]$ 的数的种类和个数，这个可以用Splay或Treap的分裂做；
但是考虑一下复杂度，这样做更新和查询答案复杂度都是 $O(\log{n})$ ，总复杂度是 $O(n \sqrt{n}\log{n})$ ；
而这类询问通常还有分块的做法，虽然查询是 $O(\sqrt{n})$ ，但更新却是 $O(1)$ 的，那么总复杂度还是 $O(n \sqrt{n})$ 的，所以这样就能跑过了；
维护还是用一个桶，但是实现是按权值分 $\sqrt{n}$ 个块，每个块维护 $\sqrt{n}$ 个元素，修改直接改；
查询分类：
1. 在一个块内：暴力查；
2. 跨块：先将头尾不完整的块暴力查，再算中间完整的块（每个块都维护了信息，所以每个块直接查）。

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
using std::sqrt;
using std::sort;
const int MAXN=100005,MAXM=1000005,MAXSQRTN=320;
int n,m;
int w[MAXN];
bool use[MAXN];
struct answer{
    int cnt,tot;
    answer(){cnt=tot=0;}
    answer& operator +=(const answer &that){
        cnt+=that.cnt,tot+=that.tot;
        return *this;
    }
}ans[MAXM];
struct query{
    int lp,rp,l,r,l_blk;
    answer *ans;
    static bool cmp(const query &a,const query &b){
        return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
    }
}qry[MAXM];
class Block{
    private:
        int m,BLK_SZ;
        int pos[MAXN],buc[MAXN];
        struct node{
            int l,r;
            answer ans;
        }d[MAXSQRTN];
        answer brute(int l,int r){
            answer ret;
            for(int i=l;i<=r;++i){
                if(buc[i]){
                    ret.cnt+=buc[i];
                    ++ret.tot;
                }
            }
            return ret;
        }
    public:
        void init(int n){
            BLK_SZ=sqrt(n)+0.5;
            m=(n-1)/BLK_SZ+1;
            for(int i=1;i<=n;++i)
                pos[i]=(i-1)/BLK_SZ+1;
            for(int i=1;i<=m;++i){
                d[i].l=(i-1)*BLK_SZ+1;
                d[i].r=i*BLK_SZ;
            }
            d[m].r=n;
        }
        void ist(int x){
            ++d[pos[x]].ans.cnt;
            if(buc[x]++==0) ++d[pos[x]].ans.tot;
        }
        void del(int x){
            --d[pos[x]].ans.cnt;
            if(--buc[x]==0) --d[pos[x]].ans.tot;
        }
        answer qry(int l,int r){
            answer ret;
            if(pos[l]==pos[r]) ret=brute(l,r);
            else{
                for(int i=pos[l]+1;i<pos[r];++i)
                    ret+=d[i].ans;
                ret+=brute(l,d[pos[l]].r);
                ret+=brute(d[pos[r]].l,r);
            }
            return ret;
        }
}blk;
inline void add(int u){
    if(use[u]) blk.del(w[u]),use[u]=false;
    else blk.ist(w[u]),use[u]=true;
}
inline void MoCpt(){
    blk.init(n);
    sort(qry+1,qry+m+1,query::cmp);
    for(int i=1,l=1,r=0;i<=m;++i){
        while(l<qry[i].lp) add(l++);
        while(l>qry[i].lp) add(--l);
        while(r<qry[i].rp) add(++r);
        while(r>qry[i].rp) add(r--);
        *qry[i].ans=blk.qry(qry[i].l,qry[i].r);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    int BLK_SZ=sqrt(n)+0.5;
    for(int i=1;i<=n;++i)
        scanf("%d",&w[i]);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d%d",&qry[i].lp,&qry[i].rp,&qry[i].l,&qry[i].r);
        qry[i].l_blk=qry[i].lp/BLK_SZ;
        qry[i].ans=&ans[i];
    }
    MoCpt();
    for(int i=1;i<=m;++i)
        printf("%d %d\n",ans[i].cnt,ans[i].tot);
    return 0;
}

丧病卡空间版（只问了种类数，没有询问个数）：[BZOJ 3809] Gty的二逼妹子序列
不过挺巧妙的，将询问的块和桶的块需要用的位置数组合并了，不过是题目特性使然。。。

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
using std::sqrt;
using std::sort;
const int MAXN=100005,MAXM=1000005,MAXSQRTN=320;
int n,m;
int w[MAXN],ans[MAXM],pos[MAXN];
bool use[MAXN];
struct query{
    int lp,rp,l,r;
    int *ans;
    static bool cmp(const query &a,const query &b){
        return pos[a.lp]<pos[b.lp] || (pos[a.lp]==pos[b.lp] && a.rp<b.rp);
    }
}qry[MAXM];
class Block{
    private:
        int m,BLK_SZ;
        int buc[MAXN];
        struct node{int l,r,ans;}d[MAXSQRTN];
        int brute(int l,int r){
            int ret=0;
            for(int i=l;i<=r;++i){
                if(buc[i]) ++ret;
            }
            return ret;
        }
    public:
        void init(int n){
            BLK_SZ=sqrt(n)+0.5;
            m=(n-1)/BLK_SZ+1;
            for(int i=1;i<=n;++i)
                pos[i]=(i-1)/BLK_SZ+1;
            for(int i=1;i<=m;++i){
                d[i].l=(i-1)*BLK_SZ+1;
                d[i].r=i*BLK_SZ;
            }
            d[m].r=n;
        }
        void ist(int x){if(buc[x]++==0) ++d[pos[x]].ans;}
        void del(int x){if(--buc[x]==0) --d[pos[x]].ans;}
        int qry(int l,int r){
            int ret=0;
            if(pos[l]==pos[r]) ret=brute(l,r);
            else{
                for(int i=pos[l]+1;i<pos[r];++i)
                    ret+=d[i].ans;
                ret+=brute(l,d[pos[l]].r);
                ret+=brute(d[pos[r]].l,r);
            }
            return ret;
        }
}blk;
inline void add(int u){
    if(use[u]) blk.del(w[u]),use[u]=false;
    else blk.ist(w[u]),use[u]=true;
}
inline void MoCpt(){
    blk.init(n);
    sort(qry+1,qry+m+1,query::cmp);
    for(int i=1,l=1,r=0;i<=m;++i){
        while(l<qry[i].lp) add(l++);
        while(l>qry[i].lp) add(--l);
        while(r<qry[i].rp) add(++r);
        while(r>qry[i].rp) add(r--);
        *qry[i].ans=blk.qry(qry[i].l,qry[i].r);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%d",&w[i]);
    for(int i=1;i<=m;++i){
        scanf("%d%d%d%d",&qry[i].lp,&qry[i].rp,&qry[i].l,&qry[i].r);
        qry[i].ans=&ans[i];
    }
    MoCpt();
    for(int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
    return 0;
}

带修改莫队

其实莫队可以推广到任意维度的区间问题，只是复杂度的问题；
那么如果我们把时间看做一维，带修改莫队就是二维的情况（当然前提是能快速推出 $[l \pm 1,r \pm 1]$ 在 $time \pm 1$ 的答案）；
类比普通莫队的做法，我们排序时第一关键字为左端点所在块，第二关键字为右端点所在块，第三关键字为时间；
设修改与询问同阶，类比的计算一下可知： $l$ 为 $O(nS)$ 次， $r$ 为 $O(nS+\frac{n^2}{S})$ ， $time$ 为 $O(\frac{n^3}{S^2})$ ；
由均值不等式得：当块大小为 $n^{\frac{2}{3}}$ 时，复杂度最优，为 $O(x \times n^{\frac{5}{3}})$
注意，修改操作是首要的，所以每次更新先移动时间指针。

1.[集训队互测 2011] 数颜色

裸模板题；
双倍经验：[BZOJ 2453] 维护队列

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
using std::pow;
using std::sort;
const int MAXN=10005,MAXM=MAXN,MAXC=1e6+5;
int qcnt;
int col[MAXN],lastcol[MAXN],buc[MAXC],ans[MAXM];
bool use[MAXN];
struct query{
    int tm,lp,rp,l_blk,r_blk;
    int *ans;
    static bool cmp(const query &a,const query &b){
        return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.r_blk<b.r_blk || (a.r_blk==b.r_blk && a.tm<b.tm));
    }
}qry[MAXM];
struct option{int u,precol,newcol;}opt[MAXM];
inline void ist(int u){if(buc[col[u]]++==0) ++ans[0];}
inline void del(int u){if(--buc[col[u]]==0) --ans[0];}
inline void add(int u){
    if(use[u]) del(u),use[u]=false;
    else ist(u),use[u]=true;
}
inline void mdf(int u,int c){
    if(use[u]) del(u);
    col[u]=c;
    if(use[u]) ist(u);
}
inline void MoCpt(){
    sort(qry+1,qry+qcnt+1,query::cmp);
    for(int i=1,l=1,r=0,tm=0;i<=qcnt;++i){
        while(tm<qry[i].tm)
            ++tm,mdf(opt[tm].u,opt[tm].newcol);
        while(tm>qry[i].tm)
            mdf(opt[tm].u,opt[tm].precol),--tm;
        while(l<qry[i].lp) add(l++);
        while(l>qry[i].lp) add(--l);
        while(r<qry[i].rp) add(++r);
        while(r>qry[i].rp) add(r--);
        *qry[i].ans=ans[0];
    }
}
int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    int BLK_SZ=pow(n,(double)2/3)+0.5;
    for(int i=1;i<=n;++i){
        scanf("%d",&col[i]);
        lastcol[i]=col[i];
    }
    char cmd;
    for(int i=1,x,y,tm=0;i<=m;++i){
        scanf("\n%c%d%d",&cmd,&x,&y);
        if(cmd=='Q'){
            ++qcnt;
            qry[qcnt].lp=x,qry[qcnt].rp=y;
            qry[qcnt].l_blk=x/BLK_SZ;
            qry[qcnt].r_blk=y/BLK_SZ;
            qry[qcnt].tm=tm;
            qry[qcnt].ans=&ans[qcnt];
        }
        else{
            ++tm;
            opt[tm].u=x,opt[tm].newcol=y;
            opt[tm].precol=lastcol[x];
            lastcol[x]=y;
        }
    }
    MoCpt();
    for(int i=1;i<=qcnt;++i)
        printf("%d\n",ans[i]);
    return 0;
}

树上莫队

子树查询

将序列做法推广到树上通常是将树转化为序列；
而子树操作通常是DFS序，这里很显然也适用；
那么复杂度同序列一样，仍是 $O(x \times n \sqrt{n})$

1.[Codeforces 375D] Tree and Queries

直接套模板就好了；
不过有一点需要转化，因为求的是出现次数不小于 $k$ 次的颜色种类数，所以维护的桶应是前缀和性质的。

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
using std::sqrt;
using std::sort;
const int MAXN=1e5+5,MAXM=MAXN,MAXK=MAXN,MAXC=MAXN;
int m;
int he[MAXN];
int col[MAXN];
int buc[MAXK],cnt[MAXC];
int ans[MAXM];
int lp[MAXN],rp[MAXN],id[MAXN];
bool use[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
struct query{
    int k,lp,rp,l_blk;
    int *ans;
    static bool cmp(const query &a,const query &b){
        return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
    }
}qry[MAXM];
inline void addE(int u,int v){
    static int cnt;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
void DFS(int u,int fa){
    static int idx;
    lp[u]=++idx;
    id[idx]=u;
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(v!=fa) DFS(v,u);
    }
    rp[u]=idx;
}
inline int ist(int u){++buc[++cnt[col[u]]];}
inline void del(int u){--buc[cnt[col[u]]--];}
inline void add(int u){
    if(use[u]) del(u),use[u]=false;
    else ist(u),use[u]=true;
}
inline void MoCpt(){
    sort(qry+1,qry+m+1,query::cmp);
    for(int i=1,l=1,r=0;i<=m;++i){
        while(l<qry[i].lp) add(id[l++]);
        while(l>qry[i].lp) add(id[--l]);
        while(r<qry[i].rp) add(id[++r]);
        while(r>qry[i].rp) add(id[r--]);
        *qry[i].ans=buc[qry[i].k];
    }
}
int main(){
    int n;
    scanf("%d%d",&n,&m);
    int BLK_SZ=sqrt(n)+0.5;
    for(int i=1;i<=n;++i)
        scanf("%d",&col[i]);
    for(int i=1,u,v;i<n;++i){
        scanf("%d%d",&u,&v);
        addE(u,v),addE(v,u);
    }
    DFS(1,0);
    for(int i=1,v;i<=m;++i){
        scanf("%d%d",&v,&qry[i].k);
        qry[i].lp=lp[v],qry[i].rp=rp[v];
        qry[i].l_blk=lp[v]/BLK_SZ;
        qry[i].ans=&ans[i];
    }
    MoCpt();
    for(int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
    return 0;
}

链上查询

如果询问变成了树上的链该怎么办呢？
继续考虑将树转换成序列；
但是不像子树，链 $(u,v)$ 转化到序列后，之间会有很多多余的点；
不过DFS序有很多种，考虑使用括号序列，即DFS进入和离开一个点时，都将其加进括号序列中；
那么链 $(u,v)$ 之间的多余部分都会在序列中出现两次，而我们之前写的就是add函数操作第一次是加入，操作第二次是删除，正好兼容！
但是考虑一个问题，就是当 $u \neq \text{lca}(u,v)$ （设 $lp_u<lp_v$ ）时， $\text{lca}$ 出现的位置是在 $lp_u$ 左和 $rp_v$ 右，我们需要强行加入 $\text{lca}$ 的贡献，查询完答案后再删掉；
所以我们DFS出括号序列后就可以将询问转化为询问括号序列上的区间（设 $lp_u<lp_v$ ）：

$\begin{cases} [rp_u,lp_v]\cup\{lp_{lca}\} & u \neq \text{lca}(u,v) \\ [lp_u,lp_v] & u=\text{lca}(u,v) \end{cases}$
由于括号序列长度为 $2n$ ，块的大小看似应设为 $\sqrt{2n}$ ，但考虑是渐进复杂度，其实无所谓了。不然为什么不每一题根据询问次数与序列长度的关系现推一个块大小呢？
总复杂度仍是 $O(x \times n \sqrt{n})$
其实还有一种基于树分块的做法，不过似乎没有这个好理解、直观，复杂度也没有更优。

1.[SPOJ 10707] Count on a tree II

裸的模板题；

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using std::sqrt;
using std::sort;
using std::swap;
using std::unique;
using std::lower_bound;
const int MAXN=40005,MAXM=100005;
int n,m;
int he[MAXN],col[MAXN];
int lp[MAXN],rp[MAXN],id[MAXN<<1];
int dfn[MAXN<<1],pos[MAXN],de[MAXN];
int buc[MAXN],ans[MAXM];
bool use[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
struct query{
    int lp,rp,l_blk,lca;
    int *ans;
    static bool cmp(const query &a,const query &b){
        return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.rp<b.rp);
    }
}qry[MAXM];
class SparseTab{
    private:
        int c[17][MAXN<<1];
    public:
        void init(int a[],int n){
            memcpy(c[0]+1,a+1,n<<2);
            for(int i=1,lim=log2(n);i<=lim;++i){
                for(int j=1;j+(1<<i)-1<=n;++j){
                    if(de[c[i-1][j]]<de[c[i-1][j+(1<<i-1)]])
                        c[i][j]=c[i-1][j];
                    else c[i][j]=c[i-1][j+(1<<i-1)];
                }
            }
        }
        int LCA(int u,int v){
            u=pos[u],v=pos[v];
            if(u>v) swap(u,v);
            int k=log2(v-u+1);
            if(de[c[k][u]]<de[c[k][v-(1<<k)+1]])
                return c[k][u];
            else return c[k][v-(1<<k)+1];
        }
}st;
inline void addE(int u,int v){
    static int cnt;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
void DFS(int u,int fa){
    static int idx;
    de[u]=de[fa]+1;
    dfn[++dfn[0]]=u;
    pos[u]=dfn[0];
    lp[u]=++idx;
    id[idx]=u;
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(v!=fa){
            DFS(v,u);
            dfn[++dfn[0]]=u;
        }
    }
    rp[u]=++idx;
    id[idx]=u;
}
inline void ist(int u){if(buc[col[u]]++==0) ++ans[0];}
inline void del(int u){if(--buc[col[u]]==0) --ans[0];}
inline void add(int u){
    u=id[u];
    if(use[u]) del(u),use[u]=false;
    else ist(u),use[u]=true;
}
inline void MoCpt(){
    sort(qry+1,qry+m+1,query::cmp);
    for(int i=1,l=1,r=0;i<=m;++i){
        while(l<qry[i].lp) add(l++);
        while(l>qry[i].lp) add(--l);
        while(r<qry[i].rp) add(++r);
        while(r>qry[i].rp) add(r--);
        if(qry[i].lca) add(qry[i].lca);
        *qry[i].ans=ans[0];
        if(qry[i].lca) add(qry[i].lca);
    }
}
inline void decrete(){
    static int tmp[MAXN];
    memcpy(tmp,col,sizeof(tmp));
    sort(tmp+1,tmp+n+1);
    tmp[0]=unique(tmp+1,tmp+n+1)-tmp-1;
    for(int i=1;i<=n;++i)
        col[i]=lower_bound(tmp+1,tmp+tmp[0]+1,col[i])-tmp;
}
int main(){
    scanf("%d%d",&n,&m);
    int BLK_SZ=sqrt(n)+0.5;
    for(int i=1;i<=n;++i)
        scanf("%d",&col[i]);
    decrete();
    for(int i=1,u,v;i<n;++i){
        scanf("%d%d",&u,&v);
        addE(u,v),addE(v,u);
    }
    DFS(1,0);
    st.init(dfn,dfn[0]);
    for(int i=1,u,v,lca;i<=m;++i){
        scanf("%d%d",&u,&v);
        lca=st.LCA(u,v);
        if(lp[u]>lp[v]) swap(u,v);
        if(lca==u){
            qry[i].lp=lp[u];
            qry[i].rp=lp[v];
        }
        else{
            qry[i].lp=rp[u];
            qry[i].rp=lp[v];
            qry[i].lca=lp[lca];
        }
        qry[i].l_blk=qry[i].lp/BLK_SZ;
        qry[i].ans=&ans[i];
    }
    MoCpt();
    for(int i=1;i<=m;++i)
        printf("%d\n",ans[i]);
    return 0;
}

带修改

由于我们已经把树上问题转化到序列上了，所以带修改和序列的完全上一样。

1.[WC 2013] 糖果公园

题目就是求 $\sum_{i=1}^{max\_col}\sum_{j=1}^{cnt_i}v_iw_j$ ；
那么直接套模板即可。

代码：

#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
using std::pow;
using std::swap;
using std::sort;
const int MAXN=100005,MAXM=MAXN,MAXQ=MAXN;
int qcnt;
int v[MAXM],w[MAXN],col[MAXN],lastcol[MAXN];
int vis[MAXM];
int he[MAXN];
int de[MAXN],dfn[MAXN<<1],pos[MAXN];
int lp[MAXN],rp[MAXN],id[MAXN<<1];
long long ans[MAXQ];
bool use[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
struct option{int u,newcol,precol;}opt[MAXQ];
struct query{
    int tm,lp,rp,lca,l_blk,r_blk;
    long long *ans;
    static bool cmp(const query &a,const query &b){
        return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && (a.r_blk<b.r_blk || (a.r_blk==b.r_blk && a.tm<b.tm)));
    }
}qry[MAXQ];
class SparseTab{
    private:
        int c[18][MAXN<<1];
    public:
        void init(int a[],int n){
            memcpy(c[0]+1,a+1,n<<2);
            for(int i=1,lim=log2(n);i<=lim;++i){
                for(int j=1;j+(1<<i)-1<=n;++j){
                    if(de[c[i-1][j]]<de[c[i-1][j+(1<<i-1)]])
                        c[i][j]=c[i-1][j];
                    else c[i][j]=c[i-1][j+(1<<i-1)];
                }
            }
        }
        int LCA(int u,int v){
            u=pos[u],v=pos[v];
            if(u>v) swap(u,v);
            int k=log2(v-u+1);
            if(de[c[k][u]]<de[c[k][v-(1<<k)+1]])
                return c[k][u];
            else return c[k][v-(1<<k)+1];
        }
}st;
inline void addE(int u,int v){
    static int cnt;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
void DFS(int u,int fa){
    static int idx;
    de[u]=de[fa]+1;
    dfn[++dfn[0]]=u;
    pos[u]=dfn[0];
    lp[u]=++idx;
    id[idx]=u;
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(v!=fa){
            DFS(v,u);
            dfn[++dfn[0]]=u;
        }
    }
    rp[u]=++idx;
    id[idx]=u;
}
inline void ist(int u){
    ans[0]+=(long long)v[col[u]]*w[++vis[col[u]]];
}
inline void del(int u){
    ans[0]-=(long long)v[col[u]]*w[vis[col[u]]--];
}
inline void add(int u){
    u=id[u];
    if(use[u]) del(u),use[u]=false;
    else ist(u),use[u]=true;
}
inline void mdf(int u,int c){
    if(use[u]) del(u);
    col[u]=c;
    if(use[u]) ist(u);
}
inline void MoCpt(){
    sort(qry+1,qry+qcnt+1,query::cmp);
    for(int i=1,l=1,r=0,tm=0;i<=qcnt;++i){
        while(tm<qry[i].tm)
            ++tm,mdf(opt[tm].u,opt[tm].newcol);
        while(tm>qry[i].tm)
            mdf(opt[tm].u,opt[tm].precol),--tm;
        while(l<qry[i].lp) add(l++);
        while(l>qry[i].lp) add(--l);
        while(r<qry[i].rp) add(++r);
        while(r>qry[i].rp) add(r--);
        if(qry[i].lca) add(qry[i].lca);
        *qry[i].ans=ans[0];
        if(qry[i].lca) add(qry[i].lca);
    }
}
int main(){
    int n,m,q;
    scanf("%d%d%d",&n,&m,&q);
    int BLK_SZ=pow(n,(double)2/3)+0.5;
    for(int i=1;i<=m;++i)
        scanf("%d",&v[i]);
    for(int i=1;i<=n;++i)
        scanf("%d",&w[i]);
    for(int i=1,u,v;i<n;++i){
        scanf("%d%d",&u,&v);
        addE(u,v),addE(v,u);
    }
    DFS(1,0);
    st.init(dfn,dfn[0]);
    for(int i=1;i<=n;++i){
        scanf("%d",&col[i]);
        lastcol[i]=col[i];
    }
    for(int i=1,t,x,y,lca,tm=0;i<=q;++i){
        scanf("%d%d%d",&t,&x,&y);
        if(t==0){
            ++tm;
            opt[tm].u=x;
            opt[tm].newcol=y;
            opt[tm].precol=lastcol[x];
            lastcol[x]=y;
        }
        else{
            ++qcnt;
            qry[qcnt].tm=tm;
            qry[qcnt].ans=&ans[i];
            lca=st.LCA(x,y);
            if(lp[x]>lp[y]) swap(x,y);
            if(lca==x){
                qry[qcnt].lp=lp[x];
                qry[qcnt].rp=lp[y];
            }
            else{
                qry[qcnt].lp=rp[x];
                qry[qcnt].rp=lp[y];
                qry[qcnt].lca=lp[lca];
            }
            qry[qcnt].l_blk=qry[qcnt].lp/BLK_SZ;
            qry[qcnt].r_blk=qry[qcnt].rp/BLK_SZ;
        }
    }
    MoCpt();
    for(int i=1;i<=q;++i){
        if(ans[i]) printf("%lld\n",ans[i]);
    }
    return 0;
}

2.[BZOJ 4129] Haruna’s Breakfast

题目要求最小的未出现的自然数，一个简单的想法就是用一个桶维护哪些值出现了；
但是题目中的值范围是 $[0,10^9]$ ，直接做不管什么实现方式的桶都不可接受；
但是我们仔细思考一下，即使每个节点的值都不同，最多只有 $n$ 个值。如果它们值域是 $[0,n]$ ，那么肯定空出来一个，且这个就是答案。如果最大值大于 $n$ ，那么 $[0,n]$ 里面空的部分更多，答案更不可能是更大的数；
因此，我们只需要维护一个以值为下标、值域为 $[0,n]$ 的桶即可；
同时，像之前的查询修改不是 $O(1)$ 的情况一样，分块的效果比线段树好；
不过我们这里桶的块大小还是 $O(\sqrt{n})$ 合适，总复杂度是 $O(n^{\frac{5}{3}})$ ，带修改的话瓶颈仍是指针移动，且更明显。

代码：

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using std::pow;
using std::sqrt;
using std::sort;
using std::swap;
using std::ceil;
const int MAXN=5e4+5,MAXM=MAXN,MAXSQRTN=225;
int n,qcnt;
int he[MAXN],w[MAXN],lastw[MAXN];
int de[MAXN],pos[MAXN],dfn[MAXN<<1];
int lp[MAXN],rp[MAXN],id[MAXN<<1];
int ans[MAXM];
bool use[MAXN];
struct line{int to,nex;}ed[MAXN<<1];
struct query{
    int lp,rp,l_blk,r_blk,tm,lca;
    int *ans;
    static bool cmp(const query &a,const query &b){
        return a.l_blk<b.l_blk || (a.l_blk==b.l_blk && a.r_blk<b.r_blk || (a.r_blk==b.r_blk && a.tm<b.tm));
    }
}qry[MAXM];
struct option{int u,prew,neww;}opt[MAXM];
class SparseTab{
    private:
        int c[17][MAXN<<1];
    public:
        void init(int a[],int n){
            memcpy(c[0]+1,a+1,n<<2);
            for(int i=1,lim=log2(n);i<=lim;++i){
                for(int j=1;j+(1<<i)-1<=n;++j){
                    if(de[c[i-1][j]]<de[c[i-1][j+(1<<i-1)]])
                        c[i][j]=c[i-1][j];
                    else c[i][j]=c[i-1][j+(1<<i-1)];
                }
            }
        }
        int LCA(int u,int v){
            u=pos[u],v=pos[v];
            if(u>v) swap(u,v);
            int k=log2(v-u+1);
            if(de[c[k][u]]<de[c[k][v-(1<<k)+1]])
                return c[k][u];
            else return c[k][v-(1<<k)+1];
        }
}st;
class Block{
    private:
        int n,m,BLK_SZ;
        int buc[MAXN];
        struct node{
            int l,r,cnt;
            int size(){return r-l+1;}
        }d[MAXSQRTN];
    public:
        void init(int n){
            this->n=n;
            BLK_SZ=sqrt(n)+0.5;
            m=(n-1)/BLK_SZ+1;
            for(int i=1;i<=n;++i)
                pos[i]=(i-1)/BLK_SZ+1;
            for(int i=1;i<=m;++i){
                d[i].l=(i-1)*BLK_SZ+1;
                d[i].r=i*BLK_SZ;
            }
            d[m].r=n;
        }
        void ist(int x){
            if(x<=n && buc[x]++==0)
                ++d[pos[x]].cnt;
        }
        void del(int x){
            if(x<=n && --buc[x]==0)
                --d[pos[x]].cnt;
        }
        int qry(){
            int cur;
            for(cur=1;cur<=m;++cur){
                if(d[cur].cnt<d[cur].size())
                    break;
            }
            for(int i=d[cur].l;i<=d[cur].r;++i){
                if(buc[i]==0) return i;
            }
        }
}blk;
inline void addE(int u,int v){
    static int cnt;
    ed[++cnt]=(line){v,he[u]};
    he[u]=cnt;
}
void DFS(int u,int fa){
    static int idx;
    de[u]=de[fa]+1;
    dfn[++dfn[0]]=u;
    pos[u]=dfn[0];
    lp[u]=++idx;
    id[idx]=u;
    for(int i=he[u],v;i;i=ed[i].nex){
        v=ed[i].to;
        if(v!=fa){
            DFS(v,u);
            dfn[++dfn[0]]=u;
        }
    }
    rp[u]=++idx;
    id[idx]=u;
}
inline void add(int u){
    u=id[u];
    if(use[u]) blk.del(w[u]),use[u]=false;
    else blk.ist(w[u]),use[u]=true;
}
inline void mdf(int u,int x){
    if(use[u]) blk.del(w[u]);
    w[u]=x;
    if(use[u]) blk.ist(w[u]);
}
inline void MoCpt(){
    blk.init(n+1);
    sort(qry+1,qry+qcnt+1,query::cmp);
    for(int i=1,l=1,r=0,tm=0;i<=qcnt;++i){
        while(tm<qry[i].tm)
            ++tm,mdf(opt[tm].u,opt[tm].neww);
        while(tm>qry[i].tm)
            mdf(opt[tm].u,opt[tm].prew),--tm;
        while(l<qry[i].lp) add(l++);
        while(l>qry[i].lp) add(--l);
        while(r<qry[i].rp) add(++r);
        while(r>qry[i].rp) add(r--);
        if(qry[i].lca) add(qry[i].lca);
        *qry[i].ans=blk.qry();
        if(qry[i].lca) add(qry[i].lca);
    }
}
int main(){
    int m;
    scanf("%d%d",&n,&m);
    int BLK_SZ=pow(n,(double)2/3)+0.5;
    for(int i=1;i<=n;++i){
        scanf("%d",&w[i]);
        lastw[i]=++w[i];
    }
    for(int i=1,u,v;i<n;++i){
        scanf("%d%d",&u,&v);
        addE(u,v),addE(v,u);
    }
    DFS(1,0);
    st.init(dfn,dfn[0]);
    for(int i=1,cmd,x,y,tm=0,lca;i<=m;++i){
        scanf("%d%d%d",&cmd,&x,&y);
        if(cmd==0){
            ++tm;
            opt[tm].u=x,opt[tm].neww=++y;
            opt[tm].prew=lastw[x];
            lastw[x]=y;
        }
        else{
            ++qcnt;
            lca=st.LCA(x,y);
            if(lp[x]>lp[y]) swap(x,y);
            if(lca==x){
                qry[qcnt].lp=lp[x];
                qry[qcnt].rp=lp[y];
            }
            else{
                qry[qcnt].lp=rp[x];
                qry[qcnt].rp=lp[y];
                qry[qcnt].lca=lp[lca];
            }
            qry[qcnt].l_blk=qry[qcnt].lp/BLK_SZ;
            qry[qcnt].r_blk=qry[qcnt].rp/BLK_SZ;
            qry[qcnt].tm=tm;
            qry[qcnt].ans=&ans[qcnt];
        }
    }
    MoCpt();
    for(int i=1;i<=qcnt;++i)
        printf("%d\n",ans[i]-1);
    return 0;
}