学习笔记：根号分治（优雅的暴力）

根号分治

       根号分治，与其说是一种算法，更不如说是一种 思想。它是将问题按照不同的数据规模划分，分别使用 不同 的算法进行求解。一般是将规模按照 根号 分组，已达到 根号平衡 的目的。一般来说，一些题目并不难想到使用根号分治去解决，但是根号分治需要 根据具体问题设计具体算法，是很灵活的。因此想到了使用根号分治并不是难点，难点是如何 分段 进行求解。

例题选讲

哈希冲突

题目

简要题意：
        给你一个长度为 $n$ 的序列 $a_i$，$m$ 次操作。操作有两种：
        $A$ 操作：给你 $x$ 和 $y$，询问序列里所有下标 模 $x$ 等于 $y$ 的元素之和。
        $B$ 操作：给你 $x$ 和 $y$，把序列里下标为 $x$ 的元素的值修改成 $y$。

        $1\le n,m\le 150000，1\le a_i\le 1000$。

分析：

       这是根号分治的入门题。

       对于询问而言：
       不难想到当 $x\ge \sqrt{n}$ 时，我们可以从 $y$ 暴力每次往后跳 $x$ 个单位，然后统计一下当前位置的元素之和就好了。时间复杂度是 $O(\sqrt{n})$。
       那么如果 $x<\sqrt{n}$ 呢？暴力往后跳的复杂度无法保证，我们考虑换一种算法。发现此时 $x$ 的取值只有 $\sqrt{n}$ 种。我们预处理出一个 $f$ 数组。 $f_{x,y}$ 表示模 $x$ 为 $y$ 的所有位置的元素之和。那么 $f$ 数组的空间复杂度是 $O(n)$ 的，预处理的时间复杂度是 $O(n\sqrt{n})$ 的。每次询问直接 $O(1)$ 输出就好了。
       对于修改而言。
       我们发现修改会对 $f$ 数组的值造成影响。因为数组的第一维只有 $\sqrt{n}$ 的规模，我们直接暴力修改 $f$ 数组。具体来讲，我们枚举数组的第一维 $x$，然后设当前位置是 $p$，$y=p\%x$。那么直接让 $f_{x,y}$ 减去修改前的元素大小，再加上修改后的元素大小就好了。时间复杂度 $O(\sqrt{n})$。

       这样整体时间复杂度就是 $O((n+q)\sqrt{n})$，空间复杂度是 $O(n)$。可以通过。

CODE：

#include
#define N 160000
#define LL long long
using namespace std;
int n, m, val[N], f[410][410], x, y;
char op;
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) scanf("%d", &val[i]);
	for(int i = 1; i <= 400; i++){
		for(int j = 1; j <= n; j++){
			f[i][j % i] += val[j];
		}
	}
	for(int i = 1; i <= m; i++){
		scanf("\n%c%d%d", &op, &x, &y);
		if(op == 'A'){
			if(x > 400){
				int sum = 0;
				for(int j = y; j <= n; j += x) sum += val[j];
				printf("%d\n", sum);
			}
			else printf("%d\n", f[x][y]);
		}
		else{
			for(int i = 1; i <= 400; i++){
				f[i][x % i] -= val[x];
				f[i][x % i] += y;
			}
			val[x] = y;
		}
	}
	return 0;
}
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

Time to Raid Cowavans

题目
简要题意：
       给一个序列 $a$， $m$ 次询问，每次询问 $t$， $k$。求 $a_t+a_{t+k}+...+a_{t+pk}$。其中 $t+pk\le n$ 且 $t+(p+1)k>n$。
       $1\le n,m\le 300000,1\le a_i\le 10^9$。
       时间限制： $4s$，空间限制： $68.36MB$。

分析：
       发现这道题 往后跳 的操作与上一道题类似。我们仍然能够想到：
       当 $k\ge \sqrt{n}$ 时，我们可以直接暴力往后跳。那么一次询问的时间复杂度就是 $O(\sqrt{n})$ 的。
       当 $k<\sqrt{n}$ 时，那么 $k$ 的取值仍然是小于 $\sqrt{n}$ 的，我们可以维护一个 $f_{i,j}$ 数组，表示 步长为 $i$，起点为 $j$ 的答案。可以用递推来求出 $f$ 数组。
       但是事情好像并没有那么简单，这样空间复杂度是 $O(n\sqrt{n})$ 的，显然是会被卡的。
       我们发现这一道题相对于上一道题 没有修改操作。考虑 离线。我们把询问按照步长从小到大排序：
       如果当前步长跟上一次不一样并且小于 $\sqrt{n}$，那么我们 $O(n)$ 跑一遍每一个点作为起点的答案，存到 $f_i$ 数组中。
       如果当前步长跟上一次一样并且小于 $\sqrt{n}$，那么我们直接 $O(1)$ 输出 $f$ 数组里面的值就好了。
       如果当前步长大于 $\sqrt{n}$，那么我们暴力跳。

       这样时间复杂度 $O(n\sqrt{n})$，空间复杂度 $O(n)$。可以通过了。

CODE：

#include
#define N 300100
#define LL long long
using namespace std;
int n, m;
LL a[N], f[N * 2], ans[N];
struct query{
	int t, k, id;
	bool operator < (query const &a)const{
		return k < a.k;
	}
}q[N];
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	scanf("%d", &m);
	for(int i = 1; i <= m; i++) scanf("%d%d", &q[i].t, &q[i].k), q[i].id = i;
	sort(q + 1, q + m + 1);
	for(int i = 1; i <= m; i++){
		if(q[i].k < 548){
			if(q[i].k != q[i - 1].k){
				for(int j = n; j >= 1; j--){
					f[j] = f[j + q[i].k] + a[j];
				}
			}
			ans[q[i].id] = f[q[i].t];
		}
		else{
			LL sum = 0;
			for(int j = q[i].t; j <= n; j += q[i].k) sum += a[j];
			ans[q[i].id] = sum;
		}
	}
	for(int i = 1; i <= m; i++) printf("%lld\n", ans[i]);
	return 0;
}
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

[ARC150B] Make Divisible

题面

简要题意：
       给定两个正整数 $A,B$，求满足 $B+Y$ 是 $A+X$ 倍数的非负整数 $X,Y$ 中，$X+Y$ 的最小值。
       $T$ 组数据。
       数据规模： $1\le T\le 100,1\le A,B\le 10^9$。

分析：

       这道题很不好想。
       首先如果 $B\le A$，那么答案就是 $A-B$。
       否则，可以令 $X=0$，那么 $Y\le A$。这也就意味着答案不会超过 $A$。
       另外我们可以想到：如果我们枚举 $X$，那么可以在 $O(1)$ 的复杂度内算出合法的最小的 $Y$。因此考虑 根号分治：
       当 $A\le \sqrt{B}$ 时，我们枚举 $X$，然后 $O(1)$ 算出一个 $Y$ 跟答案取 $min$。这里 $X$ 的枚举范围是 $[0,A]$，时间复杂度 $O(\sqrt{B})$。
       当 $A>\sqrt{B}$，那么容易注意到 $\frac{B}{A}<\sqrt{B}$。我们思考能否根据这一点做文章。
       如果有性质 $\frac{B+Y}{A+X}\le \frac{B}{A}$ 并且如果我们 知道比值可以快速算出最小的合法 $X$ 和 $Y$ 的话，那么问题可以解决。
       这里证明一下性质：对于最优的 $Y$ 和 $X$，$\frac{B+Y}{A+X}\le \lceil \frac{B}{A}\rceil$。
       设 $d=\lceil \frac{B}{A}\rceil ,d^{\prime }=\frac{B+Y}{A+X}$。
       假设 $d^{\prime }>d$。
       那么 $d^{\prime }(A+X)\ge (d+1)(A+X)$
       即 $B+Y\ge (d+1)A+dX$
       $B+Y\ge B+A+dX$
       $Y\ge A+dX$
       $Y>A$
       因为 $Y$ 一定小于等于 $A$。所以假设不成立。证毕。

       还有一个问题，就是如果我们知道比值该怎么算 $X,Y$ 呢？
       我们设 $\frac{B+Y}{A+X}=d$，那么就有：
       $B+Y=d(A+X)$
       $Y=dA+dX-B$
       $X+Y=(d+1)X+dA-B$
       发现这是一个关于 $X$ 的一次函数，我们只要求出最小的 $X$ 就好了。
       这个只需要找到最小的 $X$，满足 $d(A+X)\ge B$ 就好了，时间复杂度可以做到 $O(1)$。

       因此总时间复杂度 $O(T\times \sqrt{B})$。

#include//根号好题 
#define LL long long
using namespace std;
int T;
LL a, b;
int main(){
	cin >> T;
	while(T--){
		cin >> a >> b;
		if(a >= b) cout << a - b << endl;//a >= b  那么Y = a - b 就好了
		else{
			LL k = sqrt(1.0 * b);
			if(a <= k){// a <= √b, 答案一定不会超过a，所以偏移去找就好了 
				LL ans = b - a;
				for(LL i = 0; i <= a; i++){// 枚举X 
					if(b % (a + i) == 0) ans = min(ans, i);
					else ans = min(ans, i + (a + i) - (b % (a + i)));
				}
				printf("%lld\n", ans);
			}
			else{// a > √b, 那么 b / a < √b， 可以证明a + x / b + y <= b / a，枚举一下就可以了 
			    LL d, ans = b - a;
			    d = (b - 1LL) / a + 1LL;
			    for(LL i = 1; i <= d; i++){//枚举 d = b + y / a + x
			        LL x;
			    	if(a * i - b >= 0) x = 0;//求一下x 
					else{
						x = (b - a * i - 1LL) / i + 1LL;//向上取整
					}
					ans = min(ans, a * i - b + (i + 1) * x);
				}
				cout << ans << endl;
			}
		} 
	}
	return 0;
}
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

无向图三元环计数

题面

分析：
       详见这里

雅加达的摩天轮

题面

分析：
       我们考虑把楼看做 点，把狗的跳跃方式看做 一种边。对于点 $x$ 里的狗而言，设它的跳跃步长是 $p$，那么我们从 $x$ 向 $x+p，x-p$ 连一条长度为 $1$ 的边。向 $x+2p,x-2p$ 连一条长度为 $2$ 的边。向 $x+kp,x-kp$ 连一条长度为 $k$ 的边。
       如果每只狗的步长都大于 $\sqrt{n}$，那么显然，整个图最多有 $m\sqrt{n}$ 条边。我们直接跑 $dijkstra$ 就好了。
       但是如果狗的步长小于 $\sqrt{n}$，这样做显然会导致边数达到 $mn$。那么我们可以想到类比 $spfa$ 的思想每次拓展一步跑最短路。但是这样有一个问题，我们不确定每一个点能够使用哪一种边。我们考虑 拆点 记录状态。因为步长大于 $\sqrt{n}$ 的不用记录。因此我们把点拆成 $\sqrt{n}+1$ 个状态。 $di{s}_{i,j}$ 表示 $i$ 号点由某一个点通过 $j$ 步长到达的最优值。特别的，当 $j>\sqrt{n}$ 时，我们看做状态 $0$。然后对于每一个点而言，它内部本身就有的边我们 只在它的某一状态成为堆头时 使用，其它时候不用。然后每次使用 状态 记录的边向左右跳一步松弛一次。这样一共有 $n\sqrt{n}$ 个点，由于我们是按照 $dijkstra$ 的方式写，时间复杂度是 $O(n\sqrt{n}lo{g}_{2}n\sqrt{n})$。

CODE：

#include//考虑最短路 
#define N 31000//瓶颈在于如果 pi < √n 那么边的数量太多 
#define M 181
using namespace std;
vector< int > G[31000];
set< int > s[M];
int n, m, b, p, dis[N], st, ed, d[N][M];// d[i][j]由j状态更新出来的最小值 
int pre[N][M];
bool vis[N];
bool bok[N][M];
struct state{
	int x, f, w;
	bool operator < (const state &a)const{
		return a.w < w;
	}
};
priority_queue< state > q;// 把一个点拆成 (√n + 1) 个状态 
int main(){
	scanf("%d%d", &n, &m);
	for(int i = 0; i < m; i++){
		scanf("%d%d", &b, &p);
		G[b].push_back(p);
		if(i == 0) st = b;
		if(i == 1) ed = b;
	}
	memset(d, 0x3f, sizeof d);
	d[st][0] = 0;
	q.push((state){st, 0, 0});// 0代表没有从一个小于等于√n的边转移过来 
	while(!q.empty()){
		state u = q.top(); q.pop();
		int x = u.x, f = u.f, w = u.w;
		if(bok[x][f]) continue;
		if(!bok[x][0]){
			for(auto v : G[x]){
				if(v >= 177){//直接跑
				    int cnt = 0; 
					for(int j = x; j < n; j += v){
						if(d[j][0] > d[x][f] + cnt){
							d[j][0] = d[x][f] + cnt;
							q.push((state){j, 0, d[j][0]});
						}
						cnt++;
					}
					cnt = 0;
					for(int j = x; j >= 0; j -= v){
						if(d[j][0] > d[x][f] + cnt){
							d[j][0] = d[x][f] + cnt;
							q.push((state){j, 0, d[j][0]});
						}
						cnt++;						
					}
				}
				else{//跑一次 
					if(x - v >= 0){
						if(d[x - v][v] > d[x][f] + 1){
							d[x - v][v] = d[x][f] + 1;
							q.push((state){x - v, v, d[x - v][v]});
						}
					}
					if(x + v < n){
						if(d[x + v][v] > d[x][f] + 1){
							d[x + v][v] = d[x][f] + 1;
							q.push((state){x + v, v, d[x + v][v]});
						}
					}
				}
			}
			bok[x][0] = 1;
		} 
		if(f != 0){// 转移一次就行 
			if(x - f >= 0){
				if(d[x - f][f] > d[x][f] + 1){
					d[x - f][f] = d[x][f] + 1;
					q.push((state){x - f, f, d[x - f][f]});
				} 
			}
			if(x + f < n){
				if(d[x + f][f] > d[x][f] + 1){
					d[x + f][f] = d[x][f] + 1;
					q.push((state){x + f, f, d[x + f][f]});
				}
			}
		}
		bok[x][f] = 1;//标记已经跑了，不用重复跑 
	}
	int res = 0x3f3f3f3f;
	for(int i = 0; i < 177; i++) res = min(res, d[ed][i]);
	if(res == 0x3f3f3f3f) printf("-1\n");
	else printf("%d\n", res);
	return 0;
}
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

[ABC259Ex] Yet Another Path Counting

题面

简要题意：

       有 $N$ 行 $N$ 列的网格图，只能向下或向右走，合法路径的开端和结尾的格子上数字一样 找到合法路径条数，对 $998244353$ 取模。

       $1\le N\le 400,1\le a_i\le N^2$。

       如果枚举起点和终点，那么可以 $O(1)$ 算出一个方案数。但是这样时间复杂度是 $O(N^4)$ 的，显然过不去。
       我们考虑根号分治：
       设数字 $c$ 的格子数量为 $k$，如果 $k\le N$，那么我们直接 $k^2$ 枚举算贡献。这一部分的时间复杂度是 $O(\frac{N^2}{k}\times k^2=N^2\times k<N^3)$ 的。
       如果 $k>n$，那么会发现最多有 $\frac{N^2}{k}$ 种这样的数字。能发现 $\frac{N^2}{k}<N$，我们对于每一种这样的数字，如果能设计一种 $O(N^2)$ 的算法求解就行了。
       我们考虑每一次对于整个网格图做一遍 $DP$。设 $d{p}_{i,j}$ 表示从一个数字为 $c$ 的格子走到 $(i,j)$ 的方案数。那么转移非常简单。如果 $(i,j)$ 上的数字是 $c$，那么我们把 $d{p}_{i,j}$ 累加到答案中就好了。
       时间复杂度 $O(N^3)$。

CODE：

#include
#define LL long long
#define mod 998244353
#define N 410
#define PII pair< int, int > 
#define pb push_back
#define F first
#define S second
using namespace std;
int n, mp[N][N];
LL c[N * 2][N * 2], res, sum[N][N];//sum[i][j] 表示范围内的合法点到（i, j）的方案数 
vector< PII > vec[N * N]; 
void solve1(int k){//暴力 
	for(auto x : vec[k]){
		for(auto y : vec[k]){
			if((x.F == y.F) && (x.S == y.S)) res = (res + 1) % mod;
			else if((x.F <= y.F) && (x.S <= y.S)) res = (res + c[y.F - x.F + y.S - x.S][y.F - x.F]) % mod;
		}
	}
}
void solve2(int k){//前缀和搞一搞 
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			sum[i][j] = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			sum[i][j] = (sum[i - 1][j] + sum[i][j - 1]) % mod;
			if(mp[i][j] == k) sum[i][j] = (sum[i][j] + 1) % mod, res = (res + sum[i][j]) % mod;
		}
	}
}
int main(){
	for(int i = 0; i <= 800; i++){
		for(int j = 0; j <= i; j++){
			if(j == 0) c[i][j] = 1LL;
			else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
		}
	}
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			scanf("%d", &mp[i][j]);
			vec[mp[i][j]].pb(make_pair(i, j));
		}
	}
	for(int i = 1; i <= n * n; i++){
		if(vec[i].empty()) continue;
		else{
			if(vec[i].size() <= n) solve1(i);
			else solve2(i); 
		}
	}
	printf("%lld\n", res);
	return 0;
} 
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