莫队算法

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

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

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

1 算法思想

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

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

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

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

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

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

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

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

2 无修改莫队

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

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

Problem: 小Y的袜子

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

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

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

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

分析

这似乎是莫队的例题（

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#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;
}

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.

分析

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#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;


}

3 带修改莫队

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

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

  • 对于每个块，timetime最多变化mm次，有O(m)O(m)。总体有O(n2mB1B2)O(\frac{n^2m}{B_1B_2})。
  • 对于每个询问内，ll和rr最多变化B1B_1、B2B_2。有O(mB1+mB2)O(mB_1+mB_2)。
  • 对于不同块转移，有最大复杂度O(n)O(n)。有O(n3B1B2)O(\frac{n^3}{B_1B_2})

当m和n同阶，取B1=B2=n2/3B_1=B_2=n^{2/3}，达到复杂度O(n5/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游戏输赢就是看异或和，异或和可以看前缀异或和内有多少个值相同的点。所以它就是在问一个区间里有多少个相同点对。

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#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;
}

Problem 3289. – Mato的文件管理

4 树上莫队/转化

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

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

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

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

WC2013 糖果公园

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
#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;
}

5 树上莫队

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

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

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

树分块

BZOJ 1086 [SCOI2005]王室联邦

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

每个省至少要有BB个城市，最多只有3B3B个城市。

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

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

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

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

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

回到莫队

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

设TuT_u为uu到根节点的边集合.那么u到v的路径为TuΔTvT_u \Delta T_v.

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

TuΔTvΔ(TuΔTu′)Δ(TvΔTv′)=Tu′ΔTv′T_u \Delta T_v \Delta (T_u \Delta T_u') \Delta (T_v\Delta T_v')=T_u'\Delta T_v'

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

6 注意

  • 关于记录当前问题的区间的开闭问题，需要谨慎安排。
  • 在确认了区间开闭后，关于最初始的状态，需要谨慎安排。
学习
#莫队 #分块 #LCA
莫队算法
https://blog.chenc.me/2019/08/02/mo-s-algorithm/
作者
CC
发布于
2019年8月3日
许可协议