树上莫队

首先有一道题

王室联邦

题目大意

给定一棵树，将树分为大小范围为 $[B, 3B]$ 的连通块集，求方案

树上分块方法之一

类似贪心，用栈维护还没有在连通块中的子节点，对于递归到的当前的点 $p$ ，扫描它的子树，能拼凑就拼凑

但是注意最后可能还会有一些点（一定包括根）剩下，那么将这些点并到最后一个连通块即可

显然每个连通块都满足大小为 $[B, 3B]$

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void DFS (int root, int father) {
    int bot = top;
    for (int i = Head[root]; i; i = Link[i].next) {
        int v = Link[i].to;
        if (v == father)
            continue;
        DFS (v, root);
        if (top - bot >= B) {
            capt[++ bind] = root;
            while (top > bot)
                belong[Stack[top --]] = bind;
        }
    }
    Stack[++ top] = root;
}

树上莫队

首先用王室联邦的方法将树分块

用一个数组 $state_p$ 来维护 $p$ 点是否在当前询问的路径上，那么每次访问就将 $state_p$ 翻转，顺便修改 $ans$ ，相当于原序列上莫队的 $add, del$ 操作

那么，每次需要修改那些点呢？

假设当前处理到 $(px, py)$ ，现在需要处理 $(x, y)$ ，那么只需修改 $px$ 到 $x$ 以及 $py$ 到 $y$ 的路径上的点即可

接下来证明该操作的正确性：

令 $T (x, y)$ 表示 $x$ 到 $y$ 路径上的点集， $xor$ 操作类似位运算的异或，即有相同点则删去，无则加入

则有 $T (x, y) = T (x, root) xor T (y, root)$ （注意，这里的 $T (x, y)$ 是不包括 $lca$ 的，故 $lca$ 需单独处理）

接下来是证明
$$
\begin{aligned} &T (px, py) xor T (x, y) \\ &= [T (px, root) xor T (py, root)] xor [T (x, root) xor T (y, root)] \\ &= [T (px, root) xor T (x, root)] xor [T (py, root) xor T (y, root)] \\ &= T (px, x) xor T (py, y) \end{aligned}
$$
那么其它的修改什么的就和序列上莫队一样了

例题

[WC2013]糖果公园

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

typedef long long LL;

const int MAXN = 1e05 + 10;
const int MAXM = 1e05 + 10;
const int MAXQ = 1e05 + 10;

struct LinkedForwardStar {
    int to;

    int next;
} ;

LinkedForwardStar Link[MAXM << 1];
int Head[MAXN]= {0};
int size = 0;

void Insert (int u, int v) {
    Link[++ size].to = v;
    Link[size].next = Head[u];

    Head[u] = size;
}

int N, M, Q;
LL V[MAXN], W[MAXN];
int pcol[MAXN];
int limit;

int belong[MAXN];
int lind = 0;
int Stack[MAXN];
int top = 0;
void DFS_bel (int root, int father) {
    int bot = top;
    for (int i = Head[root]; i; i = Link[i].next) {
        int v = Link[i].to;
        if (v == father)
            continue;
        DFS_bel (v, root);
        if (top - bot >= limit) {
            lind ++;
            while (top > bot)
                belong[Stack[top --]] = lind;
        }
    }
    Stack[++ top] = root;
}

int father[MAXN]= {0};
int deep[MAXN];
int dfn[MAXN];
int value[MAXN << 1], ranking[MAXN << 1];
int dfsord = 0;
void DFS_LCA (int root, int fa) {
    father[root] = fa;
    dfn[root] = ++ dfsord;
    value[dfsord] = deep[root], ranking[dfsord] = root;
    for (int i = Head[root]; i; i = Link[i].next) {
        int v = Link[i].to;
        if (v == fa)
            continue;
        deep[v] = deep[root] + 1;
        DFS_LCA (v, root);
        value[++ dfsord] = deep[root], ranking[dfsord] = root;
    }
}
pair<int, int> ST[MAXN << 1][20];
void RMQ () {
    for (int i = 1; i <= dfsord; i ++)
        ST[i][0] = make_pair (value[i], ranking[i]);
    for (int j = 1; j <= 18; j ++)
        for (int i = 1; i + (1 << j) - 1 <= dfsord; i ++)
            ST[i][j] = ST[i][j - 1].first < ST[i + (1 << (j - 1))][j - 1].first ? ST[i][j - 1] : ST[i + (1 << (j - 1))][j - 1];
}
int LCA (int x, int y) {
    int L = dfn[x], R = dfn[y];
    if (L > R)
        swap (L, R);
    int k = log2 (R - L + 1);
    return ST[L][k].first < ST[R - (1 << k) + 1][k].first ? ST[L][k].second : ST[R - (1 << k) + 1][k].second;
}

LL ans = 0;

struct QuerySt {
    int index;
    int time;
    int x, y;

    QuerySt (int find = 0, int ftime = 0, int fx = 0, int fy = 0) :
        index (find), time (ftime), x (fx), y (fy) {}

    bool operator < (const QuerySt& p) const {
        if (belong[x] != belong[p.x])
            return belong[x] < belong[p.x];
        if (belong[y] != belong[p.y])
            return belong[y] < belong[p.y];
        return time < p.time;
    }
} ;
QuerySt Query[MAXQ];
int qind = 0;
int modposi[MAXQ], modtime[MAXQ];
int modpre[MAXQ], modval[MAXQ];
int mind = 0, cur = 0;
int state[MAXN]= {0};
int donet[MAXN]= {0};
void reverse (int p) {
    if (state[p])
        ans -= V[pcol[p]] * W[donet[pcol[p]]], donet[pcol[p]] --;
    state[p] ^= 1;
    if (state[p])
        donet[pcol[p]] ++, ans += V[pcol[p]] * W[donet[pcol[p]]];
}
void move (int u, int v) {
    int lca = LCA (u, v);
    while (u != lca)
        reverse (u), u = father[u];
    while (v != lca)
        reverse (v), v = father[v];
}
void extime (int p, int type) {
    bool exist = false;
    if (state[modposi[p]]) {
        exist = true;
        reverse (modposi[p]);
    }
    if (type == 1) {
        modpre[p] = pcol[modposi[p]];
        pcol[modposi[p]] = modval[p];
    }
    else {
        pcol[modposi[p]] = modpre[p];
    }
    if (exist)
        reverse (modposi[p]);
}
void timemod (int ptime) {
    while (cur < mind && modtime[cur + 1] <= ptime)
        extime (++ cur, 1);
    while (cur > 0 && modtime[cur] > ptime)
        extime (cur --, 2);
}
LL answer[MAXQ]= {0};
void Moqueue () {
    int px = 1, py = 1;
    for (int i = 1; i <= qind; i ++) {
        int ind = Query[i].index, time = Query[i].time;
        int x = Query[i].x, y = Query[i].y;
        timemod (time);
        move (px, x), px = x;
        move (py, y), py = y;
        int lca = LCA (px, py);
        reverse (lca);
        answer[ind] = ans;
        reverse (lca);
    }
}

int getnum () {
    int num = 0;
    char ch = getchar ();

    while (! isdigit (ch))
        ch = getchar ();
    while (isdigit (ch))
        num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

    return num;
}

int main () {
    N = getnum (), M = getnum (), Q = getnum ();
    limit = (int) ceil (pow ((double) N, 2.0 / 3.0));
    for (int i = 1; i <= M; i ++)
        V[i] = (LL) getnum ();
    for (int i = 1; i <= N; i ++)
        W[i] = (LL) getnum ();
    for (int i = 1; i < N; i ++) {
        int u = getnum (), v = getnum ();
        Insert (u, v), Insert (v, u);
    }
    for (int i = 1; i <= N; i ++)
        pcol[i] = getnum ();
    DFS_bel (1, 0);
    while (top > 0)
        belong[Stack[top --]] = lind;
    DFS_LCA (1, 0), RMQ ();
    for (int i = 1; i <= Q; i ++) {
        int opt = getnum ();
        if (opt == 0) {
            int p = getnum (), col = getnum ();
            modposi[++ mind] = p, modtime[mind] = i, modval[mind] = col;
        }
        else if (opt == 1) {
            int x = getnum (), y = getnum ();
            qind ++, Query[qind] = (QuerySt (qind, i, x, y));
        }
    }
    sort (Query + 1, Query + qind + 1);
    Moqueue ();
    for (int i = 1; i <= qind; i ++)
        printf ("%lld\n", answer[i]);

    return 0;
}

/*
4 3 5
1 9 2
7 6 5 1
2 3
3 1
3 4
1 2 3 2
1 1 2
1 4 2
0 2 1
1 1 2
1 4 2
*/

二次离线莫队

考虑某个莫队的复杂度是 $O (n\sqrt{n}T)$，其中 $x$ 是某种复杂度，即莫队在移动端点时的更新不是 $O (1)$ 而是 $O (x)$ 的，即可用二次离线莫队优化掉 $O (T)$

考虑右端点的一次由 $R_{i - 1}$ 到 $R_i (R_i > R_{i - 1})$ 的一次移动，对于 $x \in (R_{i - 1}, R_i]$，令其对区间 $[l, r]$ 的贡献为 $c (x, [l, r])$，那么也就是说 $x$ 每次移动我们需要知道 $c (x, [l, x - 1])$，差分，得
$$
c (x, [l, x - 1]) = c (x, [1, x - 1]) - c (x, [1, l - 1])
$$
对于 $c (x, [1, x - 1])$，显然可以直接前缀和维护；对于 $c (x, [1, l - 1])$，由于在一次移动中永远都是给 $[1, l - 1]$ 做贡献，那么可以只在 $l - 1$ 的位置打个标记说有哪些 $x$ 需要了解它在该区间的贡献，再计算一下就好了

也就是说第一次离线处理出 $c (x, [1, x - 1])$ 并且给每个端点打上标记说明仍需计算的区间，第二次离线则处理第一次离线分离出的区间

故总时间复杂度 $O (nT + n\sqrt{n})$，空间复杂度 $O (n)$

以 「第十四分块(前体)」 为例

题目描述：查询 $l \le i < j \le r$，且 $a_i \bigoplus a_j$ 的二进制表示下存在 $k$ 个 $1$ 的二元组 $(i, j)$ 个数

令二进制下有 $k$ 个 $1$ 的数的集合为 $A$（最多有 $3432$ 个），数字 $x$ 出现的次数为 $ap (x)$，那么加入一个数 $y$ 时所增加的贡献即为
$$
\Delta c(x, [l, r]) = \sum\limits_{x \in A} ap (x \bigoplus y)
$$
二次离线莫队即可

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

typedef long long LL;

const int MAXN = 1e05 + 10;
const int MAXM = 1e05 + 10;
const int MAXU = 16384;

int N, M, K;
int a[MAXN]= {0};
int limit = 0, bel[MAXN]= {0};
vector<int> bits;
LL buck[MAXU]= {0}, preans[MAXN]= {0};

struct querySt {
	int l, r, ind;
	LL ans;

	querySt () {}
	bool operator < (const querySt& p) const {
		return bel[l] == bel[p.l] ? r < p.r : l < p.l;
	}
} ;
querySt query[MAXM];
struct T {int l, r, delt;};
vector<T> subs[MAXN];

LL answer[MAXM]= {0};

int getnum () {
	int num = 0;
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}
inline void write (LL x) {
	if (x >= 10) write (x / 10);
	putchar (x % 10 + '0');
}

int main () {
	N = getnum (), M = getnum (), K = getnum ();
	limit = sqrt (N);
	for (int i = 1; i <= N; i ++) {
		a[i] = getnum ();
		bel[i] = (i - 1) / limit + 1;
	}
	for (int i = 1; i <= M; i ++) {
		query[i].l = getnum (), query[i].r = getnum ();
		query[i].ind = i, query[i].ans = 0;
	}
	for (int i = 0; i < 16384; i ++)
		if (__builtin_popcount (i) == K)
			bits.push_back(i);
	for (int i = 1; i <= N; i ++) {
		preans[i] = buck[a[i]];
		for (int j = 0; j < (int) bits.size(); j ++)
			buck[a[i] ^ bits[j]] ++;
	}
	sort (query + 1, query + M + 1);
	for (int i = 1, pl = 1, pr = 0; i <= M; i ++) {
		int l = query[i].l, r = query[i].r;
		if (pl < l) subs[pr].push_back((T) {pl, l - 1, - i});
		while (pl < l) query[i].ans += preans[pl], pl ++;
		if (pl > l) subs[pr].push_back((T) {l, pl - 1, i});
		while (pl > l) query[i].ans -= preans[pl - 1], pl --;
		if (pr < r) subs[pl - 1].push_back((T) {pr + 1, r, - i});
		while (pr < r) query[i].ans += preans[pr + 1], pr ++;
		if (pr > r) subs[pl - 1].push_back((T) {r + 1, pr, i});
		while (pr > r) query[i].ans -= preans[pr], pr --;
	}
	memset (buck, 0, sizeof (buck));
	for (int i = 1; i <= N; i ++) {
		for (int j = 0; j < (int) bits.size(); j ++)
			buck[a[i] ^ bits[j]] ++;
		for (int j = 0; j < (int) subs[i].size(); j ++) {
			int l = subs[i][j].l, r = subs[i][j].r, ind = subs[i][j].delt;
			for (int k = l; k <= r; k ++) {
				int tmp = buck[a[k]];
				if (k <= i && ! K) tmp --;
				if (ind > 0) query[ind].ans += tmp;
				else query[- ind].ans -= tmp;
			}
		}
	}
	for (int i = 2; i <= M; i ++) query[i].ans += query[i - 1].ans;
	for (int i = 1; i <= M; i ++) answer[query[i].ind] = query[i].ans;
	for (int i = 1; i <= M; i ++)
		write (answer[i]), puts ("");

	return 0;
}

/*
5 5 2
3 4 8 0 2
4 5
3 5
1 4
2 5
1 5
*/