【听课笔记】分块&莫队&根号分治

啊,其实就是一直听说分块很nb但是一直没有深刻理解,于是就整理了一下…

话说我分块历史上只写过一道题…蒲公英那题…当时写的还一堆诡异的边界,导致我毫无复盘的欲望…

日常不想写数据结构(1/1) 。

然而内容就是 lxl 的 PPT ,個人感覺退役之前這個 PPT 是學不完了😭

不做說明的話,全部數據的 $n,m$ 都是 $10^5$ 的。块大小记作 $B$ .

序列分块

A

维护一个序列,支持

1.区间加。

2.查询区间小于 $x$ 的数个数。

对于询问操作而言,可以发现区间加不影响块内部的顺序,所以考虑对于每个块维护块内元素排完序之后的结果,存在一个容器里,记为 $ov_x$ 。

对于修改操作,整块就直接打一个 $tag_x$ ,零散块由于至多有两块受影响,于是考虑暴力重构。暴力重构的方法大概是按顺序将 $ov_x$ 里那些要被加的元素取出,可以知道这样 $ov_x$ 和被取出的那些元素就都是有序的了,可以归并排序做到线性。所以修改复杂度是 $O(B)+O(\frac{n}{B})$ 的。

查询操作,零散块当然是暴力 for​ ,整块的话可以二分,查询复杂度 $O(B)+O(\frac{n}{B}\log B)$ 。发现如果令 $B = \sqrt{n\log B}$ ,那么总复杂度会变成 $O(m\sqrt{n\log B})$ ,可能会更优。

同时也可以把询问对于每一块都离线下来,对于每个块,在每次重构之前可以回答上一次重构之后的问题,用基数排序把这些询问排序之后,和块内元素一起归并可以做到线性。于是就可以离线 $O(m\sqrt n)$ 了。

B

维护一个序列,支持查询

1.区间加

2.查询区间k小

考虑和上一道题一样的做法,每次外层套一个二分,那么就是查询每个块内 $<x$ 的数的个数,这样还需要再二分,询问复杂度变成了 $O(\frac{n}{B}\log B\log V)$ ,平衡之后就是 $O(\sqrt{n\log B}\log V)$。

……然而 lxl 出的 YNOI 把这个 Sol 给卡了。

考虑一个 $trick$ ,就是调整块的大小。令 $B=\sqrt n \log n$ ,那么每次修改显然还是 $O(B)>O(\frac{n}{B})$ 的,查询还是用二分,但是由于整块的数量下降到了 $O(\frac{n}{\sqrt n \log n})=O(\frac{\sqrt n}{\log n})$ ,那么这部分复杂度就变成了 $O(\sqrt n\log n)$ 。看上去很不错?但是零散块查询的时候,由于有 $O(\sqrt n\log n)$ 的零散点,所以如果暴力二分就又变成俩 $\log $ 了。不过显然这些零散点是可以归并的,于是这部分的复杂度就变成了 $O(\sqrt n\log n+\log n)$ 。

最终总复杂度 $O(m\sqrt n\log n)$ 。

根号平衡

A

维护序列,要求 $O(1)$ 修改, $O(\sqrt n)$ 求区间和。

似乎就是最水的分块题。考虑分块维护块内和,修改的时候 $O(1)$ 修改点值和块值,询问就是朴素询问即可。

B

维护序列,要求 $O(\sqrt n)$ 修改, $O(1)$ 求区间和。

这个比较有意思。发现要求 $O(1)$ 求区间和,那自然就是要维护前缀和。于是就分别维护块的前缀和 and 块内部的前缀和,每次修改就是要修改之后的块的前缀和 and 散点所在块内部的前缀和,查询作差即可。

C

维护序列,要求 $O(\sqrt n)$ 区间加,$O(1)$ 询问单点。

改成维护差分就变成 B 的内容了。

D

维护序列,要求 $O(1)$ 区间加,$O(\sqrt n)$ 询问单点。

维护差分,就变成 A 了…这一波,这一波整理顺序没有决策单调性(雾)。

E

维护一个集合,支持 $O(1)$ 插入一个数,$O(\sqrt n)$ 查询 $k$ 小。

大概就是考虑值域分块。考虑把所有数字离散化之后是 $1\sim m$ ,然后按照值域分块,对于每个块记录一下这段值域出现了多少个数,每个位置出现了多少个数。插入就是在对应位置 $+1$,这个块 $+1$,询问就是 forforfor。

似乎有个小问题,就是如果值域 $1e9$ 可能要多一个二分的 log。如果不强制在线可以把询问一起离散化,但是如果强制在线可能就必须要二分了。

F

维护一个集合,支持 $O(\sqrt n)$ 插入一个数,$O(1)$ 查询 $k$ 小。

还是按值域分块。同时维护每个块的 $ov$。

那么如果要插入一个数,那么那个块本身需要重构,然后对于这之后的所有数都需要后移一位,相当于每次每个块头部删一个元素,尾部加入一个元素。查询的时候直接定位到那个块即可。

实现方面,每个块的 $ov$ 拿一个支持双端删插的容器即可。这题的关键点就在于要保证前 $k$ 个块的大小可以快速查询,那么令每个块的大小相同就是不错的选择。

[CodeChef] Chef and Churu

给 $n$ 个数,给定 $m$ 个函数,每个函数为序列中第 $l_i$ 到第 $r_i$ 个数的和。有 $q$ 个询问,两种类型的操作:

1 x y 把序列中的第 $x$ 个数改为 $y$ 。

2 x y 求第 $x$ 个函数到第 $y$ 个函数的和。

一眼感觉是什么 CDQ 🐂🍺题.jpg

草,知道正解的我眼淚掉下來,感覺好神仙啊。大概就是考虑这些函数都是静态的,所以可以对函数分块,然后维护前 $i$ 个函数里面,序列上每个元素要被算多少次,并且维护前缀函数的答案和。那么每次修改只需要 $\frac{n}{B}$ 地修改每个前缀和即可。询问的时候,整块就是直接拿前缀和作差,对于散点而言,考虑至多是 $O(B)$ 次查询,每次查询本质上是对序列上一个区间的查询。所以用那个 $O(\sqrt n)$ 单点修改 $O(1)$ 查询区间和的方式,即 B 中的技巧就好了。

最终复杂度 $O(m\sqrt n)$ 。

莫队

[AHOI2013]作业

查询区间 $[l,r]$ 中值在 $[a,b]$ 内的不同数个数

$n \leq 10^5 , m \leq 10^5$

考虑直接莫队的话,需要支持查询某个值域中的数,需要上树状数组,但这样带 $\log$ 。

于是考虑一下莫队的本质,即莫队的复杂度分析,本质上分析的是 $l,r$ 移动的复杂度,也就是修改的复杂度。所以莫队可以本质上看成一个 $O(n\sqrt m)$ 修改,$O(m)$ 询问的数据结构,也就是可以用一个可以快速修改,低速查询的 ds 来维护值域,那这自然就是值域分块,最终复杂度 $O(n\sqrt m+m\sqrt n)$ 。

然后本题需要分别维护出现次数和是否出现,分别维护即可。

不过话说回来,这东西本质上等价于查询 $pre_x<l,pos_x\in[l,r],x\in[a,b]$ 的这样的 $x$ 的个数。那么这就是一个三维数点,CDQ 套树状数组即可。

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
int B ; 
int V ;
int n, m ;
int bl[N] ;
int blv[N] ;
int res[N] ;
int ans[N] ;
int sum[N] ;
int sumr[N] ;
int sump[N] ;
int base[N] ;

struct query{
int id ;
int l, r ;
int a, b ;
}q[N] ;

bool comp(query a, query b){
return (bl[a.l] ^ bl[b.l]) ? bl[a.l] < bl[b.l] :
((bl[a.l] & 1) ? a.r < b.r : a.r > b.r) ;
}
void del(int p){
sump[base[p]] -- ;
sumr[blv[base[p]]] -- ;
if (sump[base[p]] <= 0) -- sum[blv[base[p]]] ;
}
void add(int p){
sump[base[p]] ++ ;
sumr[blv[base[p]]] ++ ;
if (sump[base[p]] <= 1) ++ sum[blv[base[p]]] ;
}
int get_ans(int l, int r){
int ret = 0 ;
r = min(r, V) ;
if (l > V) return 0 ;
int nl = blv[l] + 1 ;
int nr = blv[r] - 1 ;
if (blv[l] == blv[r]){
for (int i = l ; i <= r ; ++ i)
ret += (bool)sump[i] ; return ret ;
}
for (int i = nl ; i <= nr ; ++ i) ret += sum[i] ;
for (int i = l ; blv[i] == blv[l] && l <= V ; ++ i) ret += (bool)sump[i] ;
for (int i = r ; blv[i] == blv[r] && r >= 0 ; -- i) ret += (bool)sump[i] ;
return ret ;
}
int get_res(int l, int r){
int ret = 0 ;
r = min(r, V) ;
if (l > V) return 0 ;
int nl = blv[l] + 1 ;
int nr = blv[r] - 1 ;
if (blv[l] == blv[r]){
for (int i = l ; i <= r ; ++ i)
ret += sump[i] ; return ret ;
}
for (int i = nl ; i <= nr ; ++ i) ret += sumr[i] ;
for (int i = l ; blv[i] == blv[l] && l <= V ; ++ i) ret += sump[i] ;
for (int i = r ; blv[i] == blv[r] && r >= 0 ; -- i) ret += sump[i] ;
return ret ;
}
int main(){
cin >> n >> m ;
B = 1.0 * n / sqrt(m) + 1 ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]), V = max(V, base[i]), bl[i] = i / B ;
for (int i = 1 ; i <= m ; ++ i)
scanf("%d%d%d%d", &q[i].l, &q[i].r, &q[i].a, &q[i].b), q[i].id = i ;
sort(q + 1, q + m + 1, comp) ;
int l = 1, r = 0 ; B = sqrt(V) + 1 ;
for (int i = 0 ; i <= V ; ++ i) blv[i] = i / B ;
for (int i = 1 ; i <= m ; ++ i){
int a = q[i].a, b = q[i].b ;
while (l < q[i].l) del(l ++) ;
while (l > q[i].l) add(-- l) ;
while (r < q[i].r) add(++ r) ;
while (r > q[i].r) del(r --) ;
res[q[i].id] = get_res(a, b) ;
ans[q[i].id] = get_ans(a, b) ;
}
for (int i = 1 ; i <= m ; ++ i)
printf("%d %d\n", res[i], ans[i]) ; return 0 ;
}

AT1219 歴史の研究

給定序列,定义 $v_x$ 为 $x$ 在区间 $[l,r]$ 中的出现次数,查询一个区间中最大的 $x\times v_x$ 。

發現就是莫隊,然後要求查詢某個數的出現次數,跟上面『作業』那個題一樣,直接對值域分塊就好了。

預處理起來似乎也不是很難的樣子,對每個 $k\times x~(k=1,2,3,\cdots,cnt_x)$ 放到一起離散化就好了。 于是最后复杂度是 $O(n\sqrt m+m\sqrt n)$ 。因为滥用 vector 以及 cache 十分不友好导致慢的一匹,用了 zay 的快读也毛用没有/dk。

实现细节:

1、按照平常莫队的写法,如果先 deladd 会出现某些数出现了负数次,解决方法比较简单,判一下就好了。

2、十分神必的一点,一开始我把对每个点标号放到了对询问排序的后面,所以 T 了半天,并且自己以为是缓冲区溢出的锅…

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
#pragma G++ optimize(fast)

#pragma GCC optimize(fast)

#include <bits/stdc++.h>

using namespace std ;

typedef long long ll ;

#define il inline

#define lwb lower_bound
#define upb upper_bound

#define vint vector <int>

#define mint map <int, int>

#define minttoll map <int, ll>

const int N = 200010 ;
const int M = 200010 ;

void debug(vector <int> tp, int minn, int maxn, char v, char c){
for (int i = minn ; i <= maxn ; ++ i)
cout << tp[i] << v ; cout << c ;
}

void debug(ll *tp, int minn, int maxn, char v, char c){
for (int i = minn ; i <= maxn ; ++ i)
cout << tp[i] << v ; cout << c ;
}

void debug(int *tp, int minn, int maxn, char v, char c){
for (int i = minn ; i <= maxn ; ++ i)
cout << tp[i] << v ; cout << c ;
}

namespace IPT {

const int L = 1 << 21;
char buf[L], *front=buf, *end=buf;
char GetChar() {
if (front == end) end = buf + fread(front = buf, 1, L, stdin);
return (front == end) ? -1 : *(front++);
}
template <typename T>
inline void qr(T &x) {
char ch = GetChar(), lst = x = 0;
while (!isdigit(ch)) lst = ch, ch = GetChar();
while (isdigit(ch)) x = x * 10 + (ch ^ 48), ch = GetChar();
if (lst == '-') x = -x;
}
template <typename T>
void qra(T *const __ary, int __n) {
for (int i = 1; i <= __n; ++i) qr(__ary[i]);
}
template <typename T>
int qrs(T *p) {
T *beg = p;
do *p = GetChar(); while (!isalnum(*p));
do *(++p) = GetChar(); while (isalnum(*p));
*p = 0;
return p - beg;
}
template <typename T>
void qrdb(T &x) {
char ch = GetChar(), lst = x = 0;
while (!isdigit(ch)) lst = ch, ch = GetChar();
while (isdigit(ch)) { x = x * 10 + (ch - '0'); ch = GetChar(); }
if (ch == '.') {
ch = GetChar();
for (double t = 0.1; isdigit(ch); t *= 0.1) {
x += (t * (ch - '0'));
ch = GetChar();
}
}
if (lst == '-') x = -x;
}

}

namespace OPT {

const int L = 30;
char buf[L];

template <typename T>
inline void qw(T x, const char aft = 0) {
if (x < 0) { x = -x, putchar('-'); }
int top = 0;
do { buf[++top] = static_cast<char>(x % 10 + '0'); } while (x /= 10);
while (top) putchar(buf[top--]);
if (aft) putchar(aft);
}
template <typename T>
void qwa(T *const __ary, int __n, const char e1, const char e2) {
for (int i = 1; i < __n; ++i) qw(__ary[i], e1);
qw(__ary[__n], e2);
}
template <typename T>
void qws(T *p, const int __n, const char ed) {
for (int i = 0; i < __n; ++i) putchar(p[i]);
if (ed) putchar(ed);
}
template <typename T>
void qws(T *p, const char ed) {
while (*p) putchar(*p++);
if(ed) putchar(ed);
}

}

using IPT::qr;
using IPT::qra;
using IPT::qrs;
using IPT::qrdb;
using OPT::qw;
using OPT::qwa;
using OPT::qws;
int B ;
int L ;
int V ;
ll res ;
ll t[N] ;
int cnt ;
int n, m ;
int g[N] ;
int bl[N] ;
ll ans[M] ;
int vl[N] ;
int vr[N] ;
int buc[M] ;
int tmp[N] ;
int blv[N] ;
int sumb[N] ;
int sump[N] ;
minttoll su ;
mint bu, vu ;
vint base[N] ;
struct query{
int id ;
int l, r ;
}q[M] ;

il bool comp(const query &a, const query &b){
return (bl[a.l] ^ bl[b.l]) ? bl[a.l] < bl[b.l] :
((bl[a.l] & 1) ? a.r < b.r : a.r > b.r) ;
}
il void add(const int &p){
if (buc[tmp[p]] < 0){
++ buc[tmp[p]] ; return ;
}
int lval = base[tmp[p]][buc[tmp[p]]] ;
int val = base[tmp[p]][++ buc[tmp[p]]] ;
// cout << val << " " << lval << endl ;
sump[val] ++ ; sumb[ blv[val] ] ++ ;
sump[lval] -- ; sumb[ blv[lval] ] -- ;
}
il void del(const int &p){
if (buc[tmp[p]] <= 0 ){
-- buc[tmp[p]] ; return ;
}
// if (buc[tmp[p]] + 1 >= base[tmp[p]].size()) cout << base <<buc[tmp[p]] << " " << p << ' ' << tmp[p] <<'\n', exit(0) ;
int lval = base[tmp[p]][buc[tmp[p]]] ;
int val = base[tmp[p]][-- buc[tmp[p]]] ;
sump[val] ++ ; sumb[ blv[val] ] ++ ;
sump[lval] -- ; sumb[ blv[lval] ] -- ;
}
il int ask(){
int ob = 0 ;
for (int b = blv[V] ; b >= 0 ; -- b)
if (sumb[b] > 0) { ob = b ; break ; } if (!ob) return 0 ;
for (int p = vr[ob] ; p >= vl[ob] ; -- p) if (sump[p]) return p ;
}
int main(){
qr(n) ; qr(m) ; B = n / sqrt(m) ;
for (int i = 1 ; i <= n ; ++ i) qr(g[i]) ;
for (int i = 1 ; i <= n ; ++ i)
bu[g[i]] ++, t[++ cnt] = 1ll * g[i] * bu[g[i]] ;
// debug(t, 1, cnt, ' ', '\n') ;
sort(t + 1, t + cnt + 1) ; bu.clear() ;
for (int i = 1 ; i <= n ; ++ i){
bl[i] = i / B ; bu[g[i]] ++ ; int w ;
w = upb(t + 1, t + cnt + 1, 1ll * g[i] * bu[g[i]]) - t - 1 ;
// cout << g[i] << " " << w << '\n' ;
if (bu[g[i]] == 1){
base[w].push_back(0) ;
base[w].push_back(w) ; vu[g[i]] = w ;
}
else base[vu[g[i]]].push_back(w) ; V = max(V, w) ;
su[w] = 1ll * g[i] * bu[g[i]] ; t[w] ++ ;
}
for (int i = 1 ; i <= m ; ++ i)
qr(q[i].l), qr(q[i].r), q[i].id = i ;
sort(q + 1, q + m + 1, comp) ;
for (int i = 1 ; i <= n ; ++ i) tmp[i] = vu[g[i]] ;
// for (int i = 1 ; i <= n ; ++ i) if(buc[tmp[i]]) return 0 ; else buc[tmp[i]] ++ ;
/* for (int i = 1 ; i <= n ; ++ i){
cout << g[i] << " " << tmp[i] << '\n' ;
debug(base[tmp[i]], 0, base[tmp[i]].size() - 1, ' ', '\n') ;
}return 0 ; */
// debug(tmp, 1, n, ' ', '\n') ;
B = sqrt(V) + 1 ;
for (int i = 1 ; i <= V ; ++ i){
blv[i] = i / B + 1 ;
if (blv[i] != blv[i - 1])
vr[blv[i - 1]] = i - 1, vl[blv[i]] = i ;
}
int l = 1, r = 0 ; vr[blv[V]] = V ;
// debug(blv, 1, V, ' ', '\n') ;
// debug(vl, 1, blv[V], ' ', '\n') ;
// debug(vr, 1, blv[V], ' ', '\n') ;
// while (l <= n) add(l ++) ;// cout << l << '\n' ;
for (int i = 1 ; i <= m ; ++ i){
while (l > q[i].l) add(-- l) ;
while (r < q[i].r) add(++ r) ;
while (l < q[i].l) del(l ++) ;
while (r > q[i].r) del(r --) ;
ans[q[i].id] = su[ ask() ] ;
}
for (int i = 1 ; i <= m ; ++ i)
qw(ans[i], '\n') ; return 0 ;
}

[SNOI2017] 一个简单的询问

给你一个长度为 $N$ 的序列 $a_i$,$1\leq i\leq N$,和 $q$ 组询问,每组询问读入 $l_1,r_1,l_2,r_2$,需输出

$ \text{get}(l,r,x)$ 表示计算区间 $[l,r]$ 中,数字 $x$ 出现了多少次。

首先可以發現這東西就是在求 $\sum\limits_{i=l_1}^{r_1}\sum\limits_{j=l_2}^{r_2}[a_i=a_j]$ 。由於是 $\sum $ 的形式,那麼自然可以拆成四個詢問,即詢問

那麼就變成了四個雙端點詢問的問題了。注意到每多一個元素 $x$,就會多 $buc_x$ 個 pair,莫隊即可。

[Ynoi2016]这是我自己的发明

给一个树,$n$ 个点,有点权,初始根是 $1$ 。$m$ 个操作,每次操作:

  1. 将树根换为 $x$ 。
  2. 给出两个点 $x$,$y$,从 $x$ 的子树中选一个点,$y$ 的子树中选一个点,如果两个点点权相等,ans++,求 ans。

$n\leq 10^5,m\leq 5\times 10^5$。

發現…似乎本質上就是上面那個題。因為換根這個地方,對於某個點至多有兩種可能,就是子樹內的點為根、子樹外的點為根和自己為根。然後就可以一開始先按照操作,把所有詢問轉化成以 $1$ 為根,$dfs$ 序上的操作。然後大概就和上一道題一樣了。

需要注意的是,如果是遇到子樹內的點作為根,那麼本身就要兩個詢問,一個詢問全局的,一個減去這個子樹的,注意到詢問全局的並不需要拆,所以一個詢問最多會被拆分成 $(2+1)\times (2+1)=9$ 個詢問,最後 $m$ 可以到 $5\times 10^6$ 左右。雖然莫隊的複雜度可以接受 $m$ 比較大,但是一開始排序的 $m\log m$ 就會很慢。所以可以用基數排序來實現這個過程。

[BZOJ3920] Yunna 的禮物

給定序列,每次查询区间中出现次数 $k_1$ 小的数里面的 $k_2$ 小的数。

靠,一開始沒看見『區間』這個限制,還很好奇為什麼要上莫隊…老了老了。

看了半天題解才大概看明白,似乎是個什麼分塊套分塊的操作。大概就是對於『出現次數』的出現次數開一個桶,然後拿值域分塊來維護這個東西,但是對於每個『次數』還是需要查詢第 $k_2$ 小的數,於是就對於這個塊內的每個『次數』,外面再套一層值域分塊來維護一個固定次數處的數的排序。

這樣插入就是 $O(1)+O(1)$ ,查詢就是 $O(\sqrt n) +O(\sqrt n)$ 。看上去很棒,但是空間上會被卡…

這個地方我就很不理解…不知道為啥會被卡…不過那個什麼『分段離散化』的 trick 大概是预处理出对于某一种出现次数,所有可能的数,再将其离散化,对于离散化后的数再來值域分塊维护。這樣複雜度就是線性了。大概是什麼 vector 保存某個數出現 $k$ 次之後的新權值?大概過程就和其他博客講的,如果某個數的總出現次數 $cnt_x>i$ ,那麼就要用 $x$ 預處理 $i$ ,這是顯然的。

似乎空間被卡的原因是值域分塊的 size 要預先確定,所以不二次離散化,複雜度就會是 $n^2$ 的了。

根号分治

A

给个图

  1. 把 $x$ 点权加 $y$ 。

2.查询 $x$ 相邻的点权和。

经 典 套 路 . 总结一下的话,大概就是「小的直接做,大的打标记」这么一个套路。

具体一点,每个点维护一下询问的 $ans$,对每个点展开关于度数的根号分治,$<\sqrt m$ 的点直接加,$>\sqrt m$ 的点打标记。每次询问到一个点 $x$,由于 $\deg > \sqrt m$ 的点不超过 $\sqrt m$ 个,所以可以直接 $for$ 过去判断是否与 $x$ 相邻。

B

规定序列 $a_n$,每次给定 $x$ 和 $y$ :

查询一个区间中最小的 $|i-j|$,使得 $a_i=x,a_j=y$。

有趣的题。

考虑对于每种颜色按照出现次数分治。某个颜色 $x$ 的出现次数记作 $cnt_x$。对于 $cnt_x\leq \sqrt n$ 的可以预处理所有位置,这一部分时 $O(n)$ 空 $O(n\sqrt n)$ ,对于 $cnt_x>\sqrt n$ 的可以预处理到所有颜色的最小距离(由于是最小距离所以可以忽略区间长度的限制),这部分时 $O(n\sqrt n)$ 空 $O(n \sqrt n)$ 。

考虑询问 $(x,y)$,如果至少一个颜色的 $cnt>\sqrt n$ 那么就可以直接做,否则考虑由于两个颜色的位置都已知且数量 $<\sqrt n$,所以按顺序拿出来,对这两个序列归并一下就做完了,复杂度 $O(m\sqrt n+n\sqrt n)$ 。

C

[Ynoi2015]いまこの時の輝きを

查询一个区间乘积的约数个数。

值域 $v\leq 10^9$。

考虑 $\tau(x)=\prod (a_x+1)$ , 同时对于某个 $v$ ,素因数个数是 $\frac{\log v}{\log \log v}$ 的,所以如果暴力莫队转移的话,每次转移的复杂度是 $O(\frac{\log v}{\log \log v})$,这样最后复杂度是 $O(nv^{\frac{1}{4}}+n\sqrt m\frac{\log v}{\log \log v})$,不过被 lxl 给卡掉了。

考虑一个神奇的根号分治。对于每个数 $v$ 而言, $>\sqrt[3]v$ 的素因子至多只会有两个,在 $v=10^9$ 时,$<10^3$ 的素数也只有 $168$ 个。所以可以暴力转移这些大素数的贡献,这样转移就是 $O(1)$ 的;然后对于每次询问,只需要再暴力统计小素数的贡献即可。最终复杂度 $O(nv^{\frac{1}{4}}+m\frac{3\cdot v^{\frac{1}{3}}}{\ln v}+n\sqrt m)$ 。

D

POI2015 Odwiedziny

树,点权,多次查询,每次给 x,y,k

求从 $x$ 开始,每次跳过 $k$ 个节点跳到 $y$ 所经过节点的和。

还是根号分治。考虑对于 $k\leq \sqrt n$ ,可以预处理出 $k=1,2,3\cdots \sqrt n$ 然后每次暴力向上跳,对于 $k>\sqrt n$ ,至多需要跳 $\sqrt n$ 次,那么可以倍增求出 k 级祖先做到 $O(m\sqrt n\log n)$ ,或者长剖做到 $O(m\sqrt n)$ 。当然也可以轻重链剖,维护每条重链上深度从大到小的点的序列,这样单次复杂度就是 $O(\log k+\frac{n}{k})$ 了。

还有一种 zz 做法,记录每个点的 $1,2,3\cdots\sqrt n,2\sqrt n,3\sqrt n$ 级祖先,这样也是 $n\sqrt n + m\sqrt n$ 的了。

E

Bzoj4320 ShangHai2006 Homework

1.在人物集合 S 中加入一个 X,保证 X 在当前集合中不存在。

2.在当前的人物集合中询问所有X mod Y 最小的值

值域 $<300000$ 。

考虑对于 $<\sqrt V$ 的所有 Y ,令 $f_k$ 表示 Y = $k$ 时的答案,每次修改可以暴力维护所有 $f$,查询时 $O(1)$ 。这一部分复杂度为 $m\sqrt V$。

考虑对于 $>\sqrt V$ 的所有 Y,发现 $V$ 以内至多有 $\sqrt V$ 个 Y 的倍数,那么每次查询相当于在两个相邻的 Y 的倍数之间查询区间最小值。注意到这样最多有 $m\sqrt V$ 次查询,$m$ 次修改,所以根号平衡一下,拿一个值域分块来维护即可。

总复杂度 $O(m\sqrt V)$ 。

总结

lxl 的课件确实都是比较有意思的题目,也确实开了眼界。

想继续学啊…可惜实力不允许啊…

不知道退役之前能不能完整地把这个课件看一遍了233