「根号相关算法」

带根号的神奇算法在不卡常的题目中还是非常优秀的,下面盘点一些常用的根号算法,诸如分块,莫队算法等等,对于实现较为复杂的双 $log$ 算法,根号算法可以说是首选

分块

基本的分块就是维护每个块内的信息,然后求的时候把散的和整块的分开来求救可以了

BZOJ 2957

维护块内的单调性即可,每次查询时暴力二分

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
#include <bits/stdc++.h>
using namespace std;
const int maxb = 500;
const int maxp = 200;
double a[maxb + 10][maxp + 10], s[maxb + 10][maxp + 10];
int top[maxb + 10], size[maxb + 10];
int main() {
int n, m; scanf("%d%d", &n, &m); int tot = (n + maxp - 1) / maxp;
for (int i = 1; i <= tot; i++)
size[i] = min(n - i * maxp + maxp, maxp);
while (m--) {
int x, y; scanf("%d%d", &x, &y);
double k = double(y) / x;
int b = (x - 1) / maxp + 1;
int p = x - (b - 1) * maxp;
a[b][p] = k; top[b] = 0;
for (int i = 1; i <= size[b]; i++)
if (!top[b] || s[b][top[b]] < a[b][i]) s[b][++top[b]] = a[b][i];
int ans = 0; double maxk = 0;
for (int i = 1; i <= tot; i++) {
int p = upper_bound(s[i] + 1, s[i] + 1 + top[i], maxk) - s[i];
ans += top[i] + 1 - p; maxk = max(maxk, s[i][top[i]]);
}
printf("%d\n", ans);
}
}

BZOJ 2141

动态逆序对,对于每一个块,用一个树状数组来维护,块内暴力更新,之外树状数组查询

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e4;
const int maxb = 2e2;
const int maxs = 1e2;
int n, m;
struct BIT {
int s[maxn + 10], maxv, size;
void init(int n, int s) {
maxv = n; size = s;
}
void add(int p, int v) {
for (int i = p; i <= maxv; i += i & -i) s[i] += v;
}
ll sum(int p, ll v = 0) {
for (int i = p; i; i -= i & -i) v += s[i]; return v;
}
}c[maxb + 10];
int a[maxn + 10], v[maxn + 10], tot; ll ans;
void change(int p, int v) {
int u = a[p], b = (p - 1) / maxs + 1;
int lp = (b - 1) * maxs + 1, rp = min(b * maxs, n);
for (int i = lp; i < p; i++)
ans -= u < a[i], ans += v < a[i];
for (int i = rp; i > p; i--)
ans -= u > a[i], ans += v > a[i];
for (int i = 1; i < b; i++) {
ans -= c[i].size - c[i].sum(u);
ans += c[i].size - c[i].sum(v);
}
for (int i = tot; i > b; i--) {
ans -= c[i].sum(u - 1);
ans += c[i].sum(v - 1);
}
c[b].add(u, -1); c[b].add(v, 1); a[p] = v;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]), v[i] = a[i];
sort(v + 1, v + 1 + n);
v[0] = unique(v + 1, v + 1 + n) - v - 1;
for (int i = 1; i <= n; i++)
a[i] = lower_bound(v + 1, v + 1 + v[0], a[i]) - v;
c[0].init(v[0], n);
for (int i = n; i; i--)
ans += c[0].sum(a[i] - 1), c[0].add(a[i], 1);
tot = (n + maxs - 1) / maxs;
for (int i = 1; i <= tot; i++) {
int lp = (i - 1) * maxs + 1, rp = min(n, i * maxs);
c[i].init(n, rp - lp + 1);
for (int j = lp; j <= rp; j++) c[i].add(a[j], 1);
}
printf("%lld\n", ans);
scanf("%d", &m);
while (m--) {
int x, y;
scanf("%d%d", &x, &y);
int u = a[x], v = a[y];
change(x, v);
change(y, u);
printf("%lld\n", ans);
}
return 0;
}

BZOJ 3295

动态逆序对,同上,代码中的块的大小已经过调整至较优值,可供参考,比什么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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5;
const int maxs = 15e2;
const int maxb = 1e2;
struct BIT {
int s[maxn + 10]; int maxv, size;
void init(int n, int v) {
maxv = n; size = v;
}
void add(int p, int v) {
for (int i = p; i <= maxv; i += i & -i) s[i] += v;
}
ll sum(int p, ll v = 0) {
for (int i = p; i; i -= i & -i) v += s[i]; return v;
}
}c[maxb + 10];
int a[maxn + 10], r[maxn + 10];
int n, m, tot; ll ans;
void erase(int p) {
int v = a[p], b = (p - 1) / maxs + 1;
int lp = (b - 1) * maxs + 1, rp = min(b * maxs, n);
for (int i = lp; i < p; i++)
ans -= a[i] ? a[i] > v : 0;
for (int i = rp; i > p; i--)
ans -= a[i] ? a[i] < v : 0;
for (int i = 1; i < b; i++)
ans -= c[i].size - c[i].sum(v);
for (int i = tot; i > b; i--)
ans -= c[i].sum(v);
c[b].add(v, -1); a[p] = 0; c[b].size--;
}
int main() {
scanf("%d%d", &n, &m); tot = (n - 1 + maxs) / maxs;
for (int i = 1; i <= n; i++) scanf("%d", &a[i]), r[a[i]] = i;
c[0].init(n, n);
for (int i = n; i; i--)
ans += c[0].sum(a[i]), c[0].add(a[i], 1);
printf("%lld\n", ans);
for (int i = 1; i <= tot; i++) {
int lp = (i - 1) * maxs + 1, rp = min(i * maxs, n);
c[i].init(n, rp - lp + 1);
for (int j = lp; j <= rp; j++) c[i].add(a[j], 1);
}
while (--m) {
int x; scanf("%d", &x); x = r[x];
erase(x); printf("%lld\n", ans);
}
return 0;
}

Powered by Hexo and Hexo-theme-hiker

Copyright © 2017 - 2018 Anoxiacxy All Rights Reserved.

UV : | PV :