莫队算法 • CC's

为了做课件又加了很多东西。

对于可以离线的区间询问问题，莫队算法提出了一种可以在 $O(n\sqrt n)$ (无修改)， $O(n^{5/3})$ (带修改)内得出答案的方法。

主要的思路是对询问离线并分块，利用在2个区间间答案的快速转移（如果无法找到快速转移的方法，就没法用了）降低复杂度。

1 算法思想#

莫队算法是由莫涛提出的算法，可以解决一类离线区间询问问题，适用性极为广泛。即,能够使用莫队算法处理的问题一般具有如下特征

区间询问
可以离线
不同区间间的答案能够较快的互推.

在满足以上条件是,通过合理的安排询问的处理顺序,能够获得一个优秀的总体复杂度。以下，假设区间的转移需要 $O(1)$

假设已知区间 $[l,r]$ 答案，有下一个需要处理的区间 $[l',r']$ 。进行答案在区间间的单步转移需要复杂度 $O(|l-l'|+|r-r'|)$ ，即转移的复杂度为二者的曼哈顿距离。那么，将所有询问点铺平在二维平面上，按曼哈顿距离生成最小生成树，如此所得到的转移代价最小。

但是一般情况下这种做法代码量较大，在代码量和时间复杂度间的妥协诞生了一个优秀的替代方案。分块。

对区间长度按根号分块，以左端点所在的分块的序号为第一关键字，右端点为第二关键字排序。那么

在同一分块，右端点递增，处理该分块所有询问右端点需要 $O(N)$ ，总体为 $O(N \sqrt N)$ 。
在分块转移，右端点最多变化 $N$ ，于是也有 $O(N \sqrt N)$ 。
在同一分块，左端点变化最多 $\sqrt N$ ，不同分块间最多变化 $\sqrt N$ ，于是N个询问有 $O(N \sqrt N)$ 。

总体复杂度 $O(N\sqrt N)$

2 无修改莫队#

以 $B=\sqrt{n}$ ，按照 $(l/B,r)$ 对询问排序。

之后枚举每一个询问，将答案在相邻询问区间间暴力的+1-1转移。

Problem: 小Y的袜子#

作为一个生活散漫的人，小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天，小Z再也无法忍受这恼人的找袜子过程，于是他决定听天由命……

具体来说，小Z把这N只袜子从1到N编号，然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双，甚至不在意两只袜子是否一左一右，他却很在意袜子的颜色，毕竟穿两只不同色的袜子会很尴尬。

你的任务便是告诉小Z，他有多大的概率抽到两只颜色相同的袜子。当然，小Z希望这个概率尽量高，所以他可能会询问多个(L,R)以方便自己选择。

袜子的数量最多为50000（是真的🐂🍺）

分析#

这似乎是莫队的例题（

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
using ll=long long;
const int MAXN=50010,MAXQ=50010;

ll gcd(ll a,ll b){
    return !b?a:gcd(b,a%b);
}
ll c2(ll n){
    if(n<2)return 0;
    return n*(n-1)/2;
}
int a[MAXN];
int block=0;
struct Q{
    int l,r;
    int i;
    ll ansu,ansd;
    bool operator<(const Q &b)const{
        if(l/block!=b.l/block)return l/block<b.l/block;
        return r<b.r;
    }
}qs[MAXQ];

int cnt[MAXN];
ll cup=0,cdown=0;
void remove(int ptr){
    cup-=c2(cnt[a[ptr]]);
    cnt[a[ptr]]--;
    cdown--;
    cup+=c2(cnt[a[ptr]]);
}
void add(int ptr){
    cup-=c2(cnt[a[ptr]]);
    cnt[a[ptr]]++;
    cdown++;
    cup+=c2(cnt[a[ptr]]);
}
int main(){
    int nlen,qlen;cin>>nlen>>qlen;
    for(int i=1;i<=nlen;i++)cin>>a[i];
    for(int i=0;i<qlen;i++)cin>>qs[i].l>>qs[i].r;
    for(int i=0;i<qlen;i++)qs[i].i=i;
    block=sqrt(nlen);
    sort(qs,qs+qlen);
    /*
    cout<<"current queries:"<<endl;
    for(auto q:qs){
        cout<<q.l<<" "<<q.r<<endl;
    }
    cout<<"====="<<endl;
*/
    int l=1,r=1;
    add(1);
    for(int i=0;i<qlen;i++){
        Q &q=qs[i];
        if(q.l==q.r){
            q.ansu=0;q.ansd=1;
            continue;
        }
        while(q.l<l)add(--l);
        while(r<q.r)add(++r);
        while(l<q.l)remove(l++);
        while(q.r<r)remove(r--);

        q.ansu=cup;
        q.ansd=cdown;
        //cout<<cup/c2(cdown)<<endl;
    }
    sort(qs,qs+qlen,[](const Q &a,const Q &b){
            return a.i<b.i;
            });
    for(int i=0;i<qlen;i++){
        if(qs[i].ansd<2){
            cout<<"0/1"<<endl;
            continue;
        }
        ll u=qs[i].ansu;
        ll d=c2(qs[i].ansd);
        ll g=gcd(u,d);
        if(g!=0)u/=g,d/=g;
        cout<<u<<"/"<<d<<endl;
    }


    return 0;
}

cpp

Problem: [HDU 6534] Chika and Friendly Pairs#

Chika gives you an integer sequence a1,a2,…,an and m tasks. For each task, you need to answer the number of ” friendly pairs” in a given interval.

friendly pair: for two integers ai and aj, if i < j and the absolute value of ai−aj is no more than a given constant integer K, then (i,j) is called a “friendly pair”.A friendly pair (i,j) in a interval [L,R] should satisfy L≤i<j≤R.

分析#

仍然是莫队，套了一个树状数组来维护答案，外加离散化解决值域问题。

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int XN = 27010, XM = 27010 * 4;

int num[XN],nL[XN],nR[XN];

int FT[XM];

int lowbit(int x) {
	return x & -x;
}
void ftadd(int pos, int x) {
	for (; pos < XM; pos += lowbit(pos))
		FT[pos] += x;
}

int ftget(int pos) {
	int res = 0;
	for (; pos; pos -= lowbit(pos))
		res += FT[pos];
	return res;
}

vector<int> vec;

struct Q {
	int l, r;
	int i;
} qs[XN];
int ans[XN];
int main()
{
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 1; i <= n; i++) {
		int x; cin >> x;
		num[i] = x;
		vec.push_back(x);
		vec.push_back(x + k);
		vec.push_back(x - k - 1);
	}
	sort(vec.begin(), vec.end());
	for (int i = 1; i <= n; i++) {
		nL[i] = lower_bound(vec.begin(), vec.end(), num[i] - k - 1) - vec.begin();
		nR[i] = lower_bound(vec.begin(), vec.end(), num[i] + k) - vec.begin();
		num[i] = lower_bound(vec.begin(), vec.end(), num[i]) - vec.begin();

		nL[i]++;
		nR[i]++;
		num[i]++;
	}

	for (int i = 0; i < m; i++) {
		Q& q = qs[i];
		cin >> q.l >> q.r;
		q.i = i;
	}
	int B = sqrt(n);
	sort(qs, qs + m, [B](const Q& a, const Q& b) {
		if (a.l / B != b.l / B)return a.l / B < b.l / B;
		return a.r < b.r;
		});
	
	int l = 1, r = 1;
	int res = 0;
	ftadd(num[l], 1);

	for (int i = 0; i < m; i++) {
		Q q = qs[i];
		while (l < q.l) {
			ftadd(num[l], -1);
			res -= ftget(nR[l]) - ftget(nL[l]);
			l++;
		}
		while (q.l < l) {
			l--;
			res += ftget(nR[l]) - ftget(nL[l]);
			ftadd(num[l], 1);
		}
		while (r < q.r) {
			r++;
			res += ftget(nR[r]) - ftget(nL[r]);
			ftadd(num[r], 1);
		}
		while (q.r < r) {
			ftadd(num[r], -1);
			res -= ftget(nR[r]) - ftget(nL[r]);
			r--;
		}
		ans[q.i] = res;
	}
	for (int i = 0; i < m; i++)cout << ans[i] << "\n";
	
	return 0;


}

cpp

3 带修改莫队#

如果对区间的查询之余，还会修改区间，且这种修改也可以快速修改、撤销。那么，可以使用莫队的一个扩展——带修改莫队实现。

假设有 $m$ 个询问，将修改操作平铺在时间线上，计算每次询问所处的时间点。将时间也作为查询的一个参数，参与分块和转移。按照 $(l/B_1,r/B_2,time)$ 对询问排序。分块有 $n^2/B_1B_2$ 个。

对于每个块， $time$ 最多变化 $m$ 次，有 $O(m)$ 。总体有 $O(\frac{n^2m}{B_1B_2})$ 。
对于每个询问内， $l$ 和 $r$ 最多变化 $B_1$ 、 $B_2$ 。有 $O(mB_1+mB_2)$ 。
对于不同块转移，有最大复杂度 $O(n)$ 。有 $O(\frac{n^3}{B_1B_2})$

当m和n同阶，取 $B_1=B_2=n^{2/3}$ ，达到复杂度 $O(n^{5/3})$ 。

枚举每一个询问，将答案在不同时间线间暴力+1-1跳转，再暴力在相邻询问的区间间+1-1转移。

~~听起来有点长寿的意思。~~

Problem: Game#

Again Alice and Bob is playing a game with stones. There are N piles of stones labelled from 1 to N, the i th pile has ai stones.

First Alice will choose piles of stones with consecutive labels, whose leftmost is labelled with L and the rightmost one is R. After, Bob will choose another consecutive piles labelled from l to r (L≤l≤r≤R). Then they’re going to play game within these piles.

Here’s the rules of the game: Alice takes first and the two will take turn to make a move: choose one pile with nonegetive stones and take at least one stone and at most all away. One who cant make a move will lose.

Bob thinks this game is not so intersting because Alice always take first. So they add a new rule, which is that Bob can swap the number of two adjacent piles’ stones whenever he want before a new round. That is to say, if the i th and i+1 pile have ai and ai+1 stones respectively, after this swapping there will be ai+1 and ai.

Before today’s game with Bob, Alice wants to know, if both they play game optimally when she choose the piles from L to R, there are how many pairs (l, r) chosed by Bob that will make Alice win.

分析#

nim游戏输赢就是看异或和，异或和可以看前缀异或和内有多少个值相同的点。所以它就是在问一个区间里有多少个相同点对。

带单点修改的区间点对计数。

代码#

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
using ll=long long;
const int MAXN=100010,MAXQ=100010;
const int MAXPOS=2e6+11;

int nlen,qlen;
int game[MAXN];
int pre[MAXN];
int modified[MAXQ],midx=0,belong[MAXN];
int block=0;
struct Q{
    int i;
    int l,r;
    int tick;

    bool operator<(const Q &b)const{
 //       if(l/block!=b.l/block)return l/block<b.l/block;
   //     if(r/block!=b.r/block)return r/block<b.r/block;
        if(belong[l]!=belong[b.l])
            return belong[l]<belong[b.l];
        if(belong[r]!=belong[b.r])
            return belong[r]<belong[b.r];
        return  tick<b.tick;
    }
}q[MAXQ];
int qidx=0;
ll cache=0;
int cnt[MAXPOS];

inline void add(int pos){
    int &c=cnt[pre[pos]];
    cache-=(ll)c*(c-1)/2;
    c++;
    cache+=(ll)c*(c-1)/2;
}
inline void rm(int pos){
    int &c=cnt[pre[pos]];
    cache-=(ll)c*(c-1)/2;
    c--;
    cache+=(ll)c*(c-1)/2;
}

int l=1,r=1,curt=0;
inline void jumpup(int tim){
    if(tim==0)return;
    int pos=modified[tim];
    int a=game[pos];
    int b=game[pos+1];
    swap(game[pos],game[pos+1]);
    if(l<=pos && pos<=r){
        rm(pos);
    }
    pre[pos]^=a;
    pre[pos]^=b;
    if(l<=pos && pos<=r){
        add(pos);
    }
}
inline void jumpdown(int tim){
    jumpup(tim);
}

ll qans[MAXQ];

int main(){
    //freopen("00.in","r",stdin);
    while(~scanf("%d%d",&nlen,&qlen)){
        block=pow(nlen,2.0/3);
        for(int i=1;i<=nlen;i++){
            scanf("%d",&game[i]);
            belong[i]=(i-1)/block;
        }
        pre[0]=0;
        for(int i=1;i<=nlen;i++)pre[i]=pre[i-1]^game[i];

        qidx=0,midx=0;
        for(int i=1;i<=qlen;i++){
            int opt;
            scanf("%d",&opt);
            if(opt==1){
                int l,r;
                scanf("%d%d",&l,&r);
                q[qidx].i=qidx;
                q[qidx].l=l;
                q[qidx].l--;
                q[qidx].r=r;
                q[qidx].tick=midx;
                qidx++;
            }else if(opt==2){
                scanf("%d",&modified[++midx]);
            }
        }
        sort(q,q+qidx);

        memset(cnt,0,sizeof(cnt));
        cache=0;
        l=r=1;curt=0;
        add(1);
        for(int i=0;i<qidx;i++){
            if(q[i].r-q[i].l+1<2){
                qans[q[i].i]=0;
                continue;
            }
            while(curt<q[i].tick)jumpup(++curt);
            while(q[i].tick<curt)jumpdown(curt--);

            while(q[i].l<l)add(--l);
            while(r<q[i].r)add(++r);
            while(l<q[i].l)rm(l++);
            while(q[i].r<r)rm(r--);
 
            //qans[q[i].i]=cache;
            ll len=r-l+1;
            qans[q[i].i]=len*(len-1)/2-cache;
        }
        for(int i=0;i<qidx;i++){
            printf("%lld\n",qans[i]);
        }
    }
    return 0;
}

cpp

Problem 3289. — Mato的文件管理

4 树上莫队/转化#

当对于树上的路径查询，每个点的贡献也能够快速加入/删除，那么莫队仍然可以做。

一种思路是把树转化为dfs序列。

将询问 $u \to v$ 先按照dfs序列对u和v换位，使得小的在前。
u是v的祖先，取u和v第一次出现的区间。
如果u不是v的祖先，取u最后一次和v的第一次出现，还需要加入lca(u,v)。

注意处理在u和v决定的区间内节点出现两次的情况。此时应认为该点不存在。

WC2013 糖果公园#

这道题就是典型的树上莫队.简单来说,在一个树上不同节点有不同的糖果,第 $i$ 种糖果本身有美味度 $V_i$ ,人们会在书上走简单路径,并品尝每个节点的糖果.同一种糖果吃多次可能会腻,定义第 $i$ 次吃同种糖果的新奇度 $W_i$ ,所以吃掉一个糖果的愉悦(偷税)度表示为糖果美味度和新奇度的乘积.在某些时刻,某些节点发的糖的类型会改变.

代码写得太长了…不过还是比较清晰的

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;
const int XN = 200010, XM = 200010;

vector<int> g[XN];

int delicious[XM];
int w[XM];
int kind[XN];
int origin[XN];

struct Q {
    int idx;
    int u, v;
    int l, r;
}qs[XN];

int in[XN], out[XN];
int ref_tick[XN];
int fa[XN][25];
int dep[XN];

int tick = 0;
void dfs(int u, int f) {
    fa[u][0] = f;
    dep[u] = dep[f] + 1;

    in[u] = ++tick;
    ref_tick[tick] = u;
    for (auto v : g[u]) {
        if (v == f)continue;
        dfs(v, u);
    }
    out[u] = ++tick;
    ref_tick[tick] = u;
}

int lca(int u, int v) {
    if (dep[u] < dep[v])swap(u, v);
    for (int p = 20; p>=0; p--) {
        if (dep[fa[u][p]] >= dep[v])
            u = fa[u][p];
    }

    if (u == v)return u;

    for (int p = 20; p>=0; p--) {
        if (fa[u][p] != fa[v][p]) {
            u = fa[u][p];
            v = fa[v][p];
        }
    }

    return fa[u][0];
}

pair<int,int> modified[XN];
int cnt[XM],inq[XN];
ll ans[XN];

int belongs[XN];

vector<int> his[XN];
int main() {
    ios::sync_with_stdio(false);
    
    memset(ans, -1, sizeof(ans));
    int n, m, q; cin >> n >> m >> q;
    for (int i = 1; i <= m; i++)cin >> delicious[i];
    for (int i = 1; i <= n; i++)cin >> w[i];
    for (int i = 0; i < n-1; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for (int i = 1; i <= n; i++)cin >> kind[i];
    for (int i = 1; i <= n; i++)origin[i] = kind[i];

    for (int i = 0; i < q; i++) {
        int opt, u, v; cin >> opt >> u >> v;
        if (opt == 0) {
            modified[i].first = u;
            modified[i].second = v;
        }
        else {
            qs[i].idx = i;
            qs[i].u = u;
            qs[i].v = v;
        }
    }

    dfs(1, 0);
    //for (int i = 1; i <= tick; i++)cout << ref_tick[i] << " ";
    //cout << endl;

    for (int p = 1; p < 20; p++) {
        for (int i = 1; i <= n; i++) {
            fa[i][p] = fa[fa[i][p - 1]][p - 1];
        }
    }

    //区间[)
    for (int i = 0; i < q; i++) {
        Q& cur = qs[i];
        if (cur.u == 0)continue;
        if (in[cur.u] > in[cur.v])swap(cur.u, cur.v);
        if (lca(cur.u, cur.v) == cur.u) {
            cur.l = in[cur.u];
            cur.r = in[cur.v]+1;
        }
        else {
            cur.l = out[cur.u];
            cur.r = in[cur.v] + 1;
        }
        //cout << cur.l << " " << cur.r << endl;
    }

    int B = pow(tick, 2.0 / 3);
    for (int i = 0; i < XN; i++) {
        belongs[i] = i / B;
    }
    sort(qs, qs + q, [=](const Q& a, const Q& b) {
        if (belongs[a.l] != belongs[b.l])return belongs[a.l] < belongs[b.l];
        if (belongs[a.r] != belongs[b.r])return belongs[a.r] < belongs[b.r];

        return a.idx < b.idx;
        });

    int L = 1, R = 1, T = 0;//T)
    ll wage=0;
    for (int i = 0; i < q; i++) {
        Q& cur = qs[i];
        //cout <<cur.idx<<","<< "from [" << L << "," << R << ") to [" << cur.l << "," << cur.r << ")" << endl;
        if (cur.l == cur.r && cur.r == 0)continue;
        //time
        while (cur.idx < T) {
            T--;
            if (modified[T].first == 0) {
                continue;
            }
            int u = modified[T].first, v = modified[T].second;
            if (inq[u]) {
                wage -= (ll)delicious[kind[u]] * w[cnt[kind[u]]];
                //cout << "remove " << u << "(" << kind[u] << ")" << (ll)delicious[kind[u]] * w[cnt[kind[u]]] << endl;
                cnt[kind[u]]--;
            }
            kind[u] = his[u].back();
            his[u].pop_back();
            if (inq[u]) {
                cnt[kind[u]]++;
                wage += (ll)delicious[kind[u]] * w[cnt[kind[u]]];
                //cout << "add " << u << "(" << kind[u] << ")" << (ll)delicious[kind[u]] * w[cnt[kind[u]]] << endl;

            }
        }
        while (cur.idx > T) {
            
            if (modified[T].first == 0) {
                T++; continue;
            }
            int u = modified[T].first, v = modified[T].second;
            if (inq[u]) {
                wage -= (ll)delicious[kind[u]] * w[cnt[kind[u]]];
                //cout << "remove " << u << "(" << kind[u] << ")" << (ll)delicious[kind[u]] * w[cnt[kind[u]]] << endl;

                cnt[kind[u]]--;
            }
            his[u].push_back(kind[u]);
            kind[modified[T].first] = modified[T].second;
            if (inq[u]) {
                cnt[kind[u]]++;
                wage += (ll)delicious[kind[u]] * w[cnt[kind[u]]];
                //cout << "add " << u << "(" << kind[u] << ")" << (ll)delicious[kind[u]] * w[cnt[kind[u]]] << endl;
            }
            T++;
        }

        //L and R
        //[)
        while (cur.l < L) {
            L--;
            int u = ref_tick[L];
            if (!inq[u]) {
                cnt[kind[u]]++;
                wage += (ll)delicious[kind[u]] * w[cnt[kind[u]]];
                //cout << "add " << u << "(" << kind[u] << ")" << (ll)delicious[kind[u]] * w[cnt[kind[u]]] << endl;
            }
            else {
                wage -= (ll)delicious[kind[u]] * w[cnt[kind[u]]];
                //cout << "remove " << u << "(" << kind[u] << ")" << (ll)delicious[kind[u]] * w[cnt[kind[u]]] << endl;
                cnt[kind[u]]--;
            }
            inq[u] ^= 1;
        }
        while (L < cur.l) {
            int u = ref_tick[L];
            if (inq[u]) {
                wage -= (ll)delicious[kind[u]] * w[cnt[kind[u]]];
                //cout << "remove " << u << "(" << kind[u] << ")" << (ll)delicious[kind[u]] * w[cnt[kind[u]]] << endl;

                cnt[kind[u]]--;
            }
            else {
                cnt[kind[u]]++;
                wage += (ll)delicious[kind[u]] * w[cnt[kind[u]]];
                //cout << "add " << u << "(" << kind[u] << ")" << (ll)delicious[kind[u]] * w[cnt[kind[u]]] << endl;

            }
            inq[u] ^= 1;

            L++;
        }
        while (cur.r < R) {
            R--;
            assert(R >= 0);
            int u = ref_tick[R];
            if (inq[u]) {
                wage -= (ll)delicious[kind[u]] * w[cnt[kind[u]]];
                //cout << "remove " << u << "(" << kind[u] << ")" << (ll)delicious[kind[u]] * w[cnt[kind[u]]] << endl;

                cnt[kind[u]]--;
            }
            else {
                cnt[kind[u]]++;
                wage += (ll)delicious[kind[u]] * w[cnt[kind[u]]];
                //cout << "add " << u << "(" << kind[u] << ")" << (ll)delicious[kind[u]] * w[cnt[kind[u]]] << endl;

            }
            inq[u] ^= 1;
        }
        while (R < cur.r) {
            int u = ref_tick[R];
            if (!inq[u]) {
                cnt[kind[u]]++;
                wage += (ll)delicious[kind[u]] * w[cnt[kind[u]]];
                //cout << "add " << u << "(" << kind[u] << ")" << (ll)delicious[kind[u]] * w[cnt[kind[u]]] << endl;

            }
            else {
                wage -= (ll)delicious[kind[u]] * w[cnt[kind[u]]];
                //cout << "remove " << u << "(" << kind[u] << ")" << (ll)delicious[kind[u]] * w[cnt[kind[u]]] << endl;

                cnt[kind[u]]--;
            }
            inq[u] ^= 1;
            R++;
        }

        ans[cur.idx] = wage;
        if (lca(cur.u, cur.v) != cur.u) {
            int l = lca(cur.u, cur.v);
            //cout << "finally add "<<l<<"("<<kind[l]<<")" << (ll)delicious[kind[l]] * (w[cnt[kind[l]] + 1]) << endl;
            ans[cur.idx] += (ll)delicious[kind[l]] * (w[cnt[kind[l]]+1]);
        }
    }

    for (int i = 0; i < q; i++) {
        if (ans[i] != -1) {
            assert(ans[i] >= 0);
            cout << ans[i] << endl;
        }
    }

    return 0;
}

cpp

5 树上莫队#

“一般来讲,树上莫队属于比较边缘化的东西,因为其所依赖的树分块处于比较尴尬的境地.”

为了进行下一种树上莫队,也就是真的直接在树上分块做莫队,我们第一个需要解决的问题是如何给树分块.我们对于块的要求仍然没有大的改变.

块内点间距离不能超过块大小
块内点数目适中
块编号相邻,块也需要连续

树分块#

BZOJ 1086 [SCOI2005]王室联邦

他想把他的国家划分成若干个省，每个省都由他们王室联邦的一个成员来管理。他的国家有个城市，编号为。一些城市之间有道路相连，任意两个不同的城市之间有且仅有一条直接或间接的道路。

每个省至少要有 $B$ 个城市，最多只有 $3B$ 个城市。

每个省必须有一个省会，这个省会可以位于省内，也可以在该省外。但是该省的任意一个城市到达省会所经过的道路上的城市（除了最后一个城市，即该省省会）都必须属于该省。

一个城市可以作为多个省的省会。

这题貌似是树分块的起源.而它的做法,就是我们将要使用的树分块的基础.其做法如下.

总体做法是使用dfs维护由子树节点组成的栈.当进入u时,记录当前栈顶,将子节点加入栈.当栈顶和之前记录的栈顶差达到分块界限时,就把它们弹出并组成一个块.这保证了块间联通,块不经过其他节点.这种做法总能保证分块大小在 $[B,2B]$ ,最后一个块大小在 $[B,3B]$ .

当v不形成新块时,说明v的栈大小小于B.而栈合并前,v的父节点u的栈也小于B,因此总体大小小于2B.
DFS完成后,可能剩余小于B个节点.这些节点加入最后一个块,从而大小小于3B.

回到莫队#

终于我们对树完成了分块.我们的总体思路仍然是离线排序,暴力转移.

设 $T_u$ 为 $u$ 到根节点的边集合.那么u到v的路径为 $T_u \Delta T_v$ .

我们的目标是从 $T_u \Delta T_v$ 到 $T_u'\Delta T_v'$ 。由于对称差满足交换律和结合律，有

T_u \Delta T_v \Delta (T_u \Delta T_u') \Delta (T_v\Delta T_v')=T_u'\Delta T_v'

所以，我们可以记录每个点是否有被算入答案，然后暴力转移从 $u \leadsto u'$ ，从 $v \leadsto v'$ ，对于在答案中的删除，对于不在答案中的加入。

6 注意#

关于记录当前问题的区间的开闭问题，需要谨慎安排。
在确认了区间开闭后，关于最初始的状态，需要谨慎安排。