学习笔记：根号分治（优雅的暴力）-USB迷|专注于互联网分享

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

文章目录

根号分治
例题选讲
- - 哈希冲突
  - Time to Raid Cowavans
  - [ARC150B] Make Divisible
  - 无向图三元环计数
  - 雅加达的摩天轮
  - [ABC259Ex] Yet Another Path Counting

根号分治

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

例题选讲

哈希冲突

题目

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

1 ≤ n , m ≤ 150000 ， 1 ≤ a i ≤ 1000 1 \leq n,m \leq 150000，1 \leq a_i \leq 1000 1≤n,m≤150000，1≤ai≤1000。

分析：

这是根号分治的入门题。

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

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

CODE：

#include<bits/stdc++.h>
#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;
}

Time to Raid Cowavans

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

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

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

CODE：

#include<bits/stdc++.h>
#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;
}

[ARC150B] Make Divisible

题面

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

分析：

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

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

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

#include<bits/stdc++.h>//根号好题 
#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 + xLL 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;
}

无向图三元环计数

题面

分析：
详见这里

雅加达的摩天轮

题面

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

CODE：

#include<bits/stdc++.h>//考虑最短路 
#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;
}

[ABC259Ex] Yet Another Path Counting

题面

简要题意：

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

1 ≤ N ≤ 400 , 1 ≤ a i ≤ N 2 1 \leq N \leq 400, 1 \leq a_i \leq N^2 1≤N≤400,1≤ai≤N2。

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

CODE：

#include<bits/stdc++.h>
#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;
}