0%

题目链接:HDU 6681

根据欧拉定理,推得答案等于交点数量加一。

下面问题变成了二维平面上有一些于坐标轴垂直的线段,求交点个数。这是一个经典的问题。

首先我们要把点的坐标离散化,注意为了加速二分的过程,可以把横坐标和纵坐标分别离散化。

接着我们把这些线段分成两类:与 \(x\) 轴平行的和与 \(y\) 轴平行的。我们需要枚举从左到右(意味着需要排序)每一根垂直于 \(x\) 轴的线段,然后对于每一根线段,在垂直于 \(y\) 轴的线段几何中,将左端点的横坐标小于或等于它的点的右端点的横坐标扔进小根堆(意味着需要排序),并对这些线段的纵坐标所在的位置加一(树状数组或线段树维护)。接着我们需要把小根堆顶部左右的右端点小于当前枚举的 \(x\) 的删掉,并并对这些线段的纵坐标所在的位置减一。那么当前的于 \(x\) 垂直的线段上的交点个数为这个线段的起点纵坐标和重点纵坐标对应的树状数组(或线段树)的一个区间和。

所以我们只需要依次枚举所有的 \(x\),将区间和叠加到答案上即可。时间复杂度 \(O(n \log n)\)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_K = 100000 + 5;
int T, n, m, K;
int cx[MAX_K], cy[MAX_K];
char dir[MAX_K];
namespace Disc {
int x[MAX_K], y[MAX_K];
int tx, ty;
void run() {
tx = ty = 0; x[++tx] = 0; y[++ty] = 0; x[++tx] = n; y[++ty] = m;
for (int i = 1; i <= K; ++i) x[++tx] = cx[i]; sort(x + 1, x + tx + 1); tx = unique(x + 1, x + tx + 1) - x - 1;
for (int i = 1; i <= K; ++i) y[++ty] = cy[i]; sort(y + 1, y + ty + 1); ty = unique(y + 1, y + ty + 1) - y - 1;
}
inline int xId(int u) {
return lower_bound(x + 1, x + tx + 1, u) - x;
}
inline int yId(int u) {
return lower_bound(y + 1, y + ty + 1, u) - y;
}
};
namespace PointSet {
struct Point {
int pos, s, e;
friend bool operator > (const Point &u, const Point &v) {
return u.e > v.e;
}
} px[MAX_K], py[MAX_K];
// px + x, py + y
int xNum, yNum;
void init() {
xNum = yNum = 0;
}
inline void insert(int ux, int uy, int vx, int vy) {
if (ux == vx) px[++xNum] = {ux, uy, vy};
if (uy == vy) py[++yNum] = {uy, ux, vx};
}
void sortCorX() {
sort(px + 1, px + xNum + 1, [](const Point &u, const Point &v){ return u.pos < v.pos; });
}
void sortCorY() {
sort(py + 1, py + yNum + 1, [](const Point &u, const Point &v){ return u.s < v.s; });
}
};
namespace BIT {
int c[MAX_K];
int maxPos;
void init(int maxPosV) {
maxPos = maxPosV;
for (int i = 0; i <= maxPos; ++i) c[i] = 0;
}
inline int lowbit(const int &u) {
return u & (-u);
}
void add(int pos, int k) {
while (pos <= maxPos) {
c[pos] += k; pos += lowbit(pos);
}
}
int sum(int pos) {
int ret = 0;
while (pos >= 1) {
ret += c[pos]; pos -= lowbit(pos);
}
return ret;
}
};
priority_queue <PointSet::Point, vector <PointSet::Point>, greater <PointSet::Point> > q;
void cal() {
scanf("%d%d%d", &n, &m, &K);
for (int i = 1; i <= K; ++i) scanf("%d %d %c", cx + i, cy + i, dir + i);
Disc::run();
PointSet::init();
int limL = Disc::xId(0), limR = Disc::xId(n), limD = Disc::yId(0), limU = Disc::yId(m);
for (int i = 1; i <= K; ++i) {
int x = Disc::xId(cx[i]), y = Disc::yId(cy[i]);
switch (dir[i]) {
case 'L': PointSet::insert(limL, y, x, y); break;
case 'R': PointSet::insert(x, y, limR, y); break;
case 'U': PointSet::insert(x, y, x, limU); break;
case 'D': PointSet::insert(x, limD, x, y); break;
}
}
BIT::init(Disc::ty);
while (!q.empty()) q.pop();
PointSet::sortCorX();
PointSet::sortCorY();
LL ans = 0;
int yPtr = 1;
for (int i = 1; i <= PointSet::xNum; ++i) {
while (yPtr <= PointSet::yNum && PointSet::py[yPtr].s <= PointSet::px[i].pos) {
q.push(PointSet::py[yPtr]);
BIT::add(PointSet::py[yPtr].pos, 1);
++yPtr;
}
while (!q.empty() && q.top().e < PointSet::px[i].pos) {
BIT::add(q.top().pos, -1);
q.pop();
}
ans += (BIT::sum(PointSet::px[i].e) - BIT::sum(PointSet::px[i].s - 1));
}
printf("%lld\n", ans + 1);
}
int main() {
scanf("%d", &T);
for (int cs = 1; cs <= T; ++cs) {
cal();
}
return 0;
}

题目链接:Codeforces 1026D

根据鸽巢原理,当抽屉数量为 \(64\) 的时候,如果大于 \(64 \times 2 + 1 = 129\) 个物品,可以保证有一个抽屉中出现三个物品。也就是说,在这一题中,我们只需要去掉所有为零的元素,在剩下的 \(r\) 个元素中随意取 \(\min \{ r, 129  \}\) 个出来寻找最小环即可。

这里可以使用 Floyd 算法求最小环,时间复杂度 \(O(129 ^ 3)\)

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
#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
typedef long long LL;
const int MAX_N = 100000 + 5;
const int MAX_V = 129 + 5;
const LL INF = LL(1E15);
int n, tot, up;
LL a[MAX_N], b[MAX_N];
LL v[MAX_V][MAX_V], d[MAX_V][MAX_V];
LL minCir = INF;
void floyd() {
for (int i = 1; i <= up; ++i) {
for (int j = 1; j <= up; ++j) {
d[i][j] = v[i][j];
}
}
for (int k = 1; k <= up; ++k) {
for (int i = 1; i < k; ++i) {
for (int j = 1; j < i; ++j) {
minCir = min(minCir, d[i][j] + v[i][k] + v[k][j]);
}
}
for (int i = 1; i <= up; ++i) {
for (int j = 1; j <= up; ++j) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%lld", a + i);
for (int i = 1; i <= n; ++i) if (a[i]) b[++tot] = a[i];
up = min(tot, 129);
for (int i = 1; i <= up; ++i) {
for (int j = i + 1; j <= up; ++j) {
if (b[i] & b[j]) {
v[i][j] = v[j][i] = 1;
} else {
v[i][j] = v[j][i] = INF;
}
}
}
floyd();
if (minCir == INF) puts("-1");
else printf("%lld\n", minCir);
return 0;
}

题目链接:BZOJ 2240

要求寻找 \(\sum_{i=1}^{n} \mu^2(i) = k\) 的最小 \(n\)

根据莫比乌斯系数容斥

\[\sum_{i=1}^{n} \mu^2(i) = \sum_{i=1}^{\lfloor \sqrt{n} \rfloor} \mu^2(i) \lfloor \frac{n}{i^2} \rfloor \]

我们可以 \(O(\sqrt{n})\) 地求小于等于 \(n\) 的无平方因子数的个数,接着二分即可,时间复杂度 \(O(T \sqrt{k} \log k)\)

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
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int MAX_N = 100000 + 5;
bool vis[MAX_N];
int mu[MAX_N], p[MAX_N], tot;
void linearSieve() {
vis[0] = vis[1] = 1;
mu[1] = 1;
for (int i = 2; i < MAX_N; ++i) {
if (!vis[i]) {
p[++tot] = i;
mu[i] = -1;
}
for (int j = 1; j <= tot && LL(i) * p[j] < MAX_N; ++j) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) break;
else mu[i * p[j]] = mu[i] * mu[p[j]];
}
}
}
int T, k;
inline LL sum(LL x) {
LL ret = 0;
LL up = sqrt(x);
for (LL i = 1; i <= up; ++i) ret += mu[i] * (x / (i * i));
return ret;
}
int main() {
linearSieve();
scanf("%d", &T);
for (int cs = 1; cs <= T; ++cs) {
scanf("%d", &k);
LL l = 1, r = LL(1E10);
while (l < r) {
LL mid = (l + r) >> 1;
LL s = sum(mid);
if (s < k) l = mid + 1;
else r = mid;
}
printf("%lld\n", l);
}
return 0;
}

题目链接:HDU 6638

传统DP的做法是用一个数组 r[u] 来维护一个行前缀和,r[u] 表示当第 \(i\) 行到第 \(j\) 行第 \(u\) 列所有元素相加的和,然后转化为一味的最大子段和,复杂度 \(O(n^3)\)

而对于题目中给出的稀疏矩阵而言,离散化之后,如果我们用线段树维护 r[u],我们发现线段树最多做两千次单点更新,均摊下来每个点的复杂度很小,复杂度 \(O(n^2 \log n)\)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
const int MAX_N = 2000 + 5;
const LL INF = LL(1E18);
int T, n, x[MAX_N], y[MAX_N], w[MAX_N];
int idx[MAX_N], idy[MAX_N], totX, totY;
vector <PII> r[MAX_N];
LL pre[MAX_N];
inline int getId(char sel, int u) {
if (sel == 'x') return lower_bound(idx + 1, idx + totX + 1, u) - idx;
if (sel == 'y') return lower_bound(idy + 1, idy + totY + 1, u) - idy;
}
// Segment Tree
LL sum[MAX_N * 4], lSum[MAX_N * 4], rSum[MAX_N * 4], mSum[MAX_N * 4];
inline int ls(int o) {
return o << 1;
}
inline int rs(int o) {
return o << 1 | 1;
}
inline void pushUp(int o) {
sum[o] = sum[ls(o)] + sum[rs(o)];
lSum[o] = max(lSum[ls(o)], lSum[rs(o)] + sum[ls(o)]);
rSum[o] = max(rSum[rs(o)], rSum[ls(o)] + sum[rs(o)]);
mSum[o] = max(max(mSum[ls(o)], mSum[rs(o)]), rSum[ls(o)] + lSum[rs(o)]);
}
void build(LL *a, int o, int l, int r) {
if (l == r) {
sum[o] = a[l];
mSum[o] = lSum[o] = rSum[o] = max(LL(-INF), a[l]);
return;
}
int mid = (l + r) >> 1;
build(a, ls(o), l, mid);
build(a, rs(o), mid + 1, r);
pushUp(o);
}
void update(int o, int l, int r, int pos, LL v) {
if (l == r) {
sum[o] = v;
mSum[o] = lSum[o] = rSum[o] = max(LL(-INF), v);
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(ls(o), l, mid, pos, v);
if (pos > mid) update(rs(o), mid + 1, r, pos, v);
pushUp(o);
}
LL query(int o, int l, int r, int L, int R) {
if (L <= l && R >= r) {
return mSum[o];
}
int mid = (l + r) >> 1;
LL ret = -INF;
if (R >= mid) ret = max(ret, query(ls(o), l, mid, L, R));
else if (L < mid) ret = max(ret, query(rs(o), mid + 1, r, L, R));
else {
ret = max(query(ls(o), l, mid, L, R), query(rs(o), mid + 1, r, L, R));
ret = max(ret, rSum[ls(o)] + lSum[rs(o)]);
}
return ret;
}
int main() {
scanf("%d", &T);
for (int cs = 1; cs <= T; ++cs) {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d%d%d", x + i, y + i, w + i);
totX = totY = 0;
for (int i = 1; i <= n; ++i) idx[++totX] = x[i], idy[++totY] = y[i];
sort(idx + 1, idx + totX + 1); sort(idy + 1, idy + totY + 1);
totX = unique(idx + 1, idx + totX + 1) - (idx + 1);
totX = unique(idy + 1, idy + totY + 1) - (idy + 1);
int xMax = 0, yMax = 0;
for (int i = 1; i <= n; ++i) xMax = max(xMax, getId('x', x[i])), yMax = max(yMax, getId('y', y[i]));
for (int i = 1; i <= xMax; ++i) r[i].clear();
for (int i = 1; i <= n; ++i) r[getId('x', x[i])].push_back({getId('y', y[i]), w[i]});
LL maxAns = -INF;
for (int i = 1; i <= xMax; ++i) {
memset(pre, 0, sizeof pre);
build(pre, 1, 1, yMax);
for (int j = i; j <= xMax; ++j) {
for (auto const &e: r[j]) pre[e.first] += e.second, update(1, 1, yMax, e.first, pre[e.first]);
maxAns = max(maxAns, mSum[1]);
}
}
printf("%lld\n", maxAns);
}
return 0;
}

题目链接:Codeforces 1199C

统计每个数字出现的个数,考虑贪心地去最大的 \(K\),删掉最少的数。对于 \(k = \lceil \log_2 K \rceil\) 固定的时候,取 $k =  _2 K $ 即 \(K = 2 ^ k\) 最大。而从 \(n k \leq 8I\) 可以看出 \(k_{\max} = \lfloor \frac{8I}{n} \rfloor\),因此我们可以求出最多可以保留多少种数(注意 \(K\) 小于等于种类总数)和最少删掉多少种数,枚举前面删几个后面删几个即可,预处理前缀和。

坑点:1<<k会爆int,应当使用1LL<<k

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 400000 + 5;
LL n, I, a[MAX_N];
LL num[MAX_N], tot;
LL pre[MAX_N], suf[MAX_N];
map <LL, LL> h;
int main() {
scanf("%lld%lld", &n, &I);
for (int i = 1; i <= n; ++i) scanf("%lld", a + i), ++h[a[i]];
for (auto const &e: h) num[++tot] = e.second;
LL k = 8 * I / n, K;
K = (k > 31 ? INT_MAX : (1LL << k));
K = min(K, tot);
for (int i = 1; i <= tot; ++i) pre[i] = pre[i - 1] + num[i];
for (int i = tot; i >= 1; --i) suf[i] = suf[i + 1] + num[i];
LL del = tot - K;
LL ans = INT_MAX;
for (int i = 0; i <= del; ++i) {
ans = min(ans, pre[i] + suf[tot - (del - i) + 1]);
}
printf("%lld\n", ans);
return 0;
}

题目链接:LOJ 2055

答案的区间是 \([1,n]\),考虑二分答案。

在check的时候我们把当前假设的答案记为 \(u\),比 \(u\) 大的位置记为 \(1\),否则记为 \(0\),得到一个新的 01 序列,用这个序列建线段树,维护区间和。当我们遇到对一个区间顺序排序的询问,就是把区间里的 1 放到区间的最后,否则把 0 放在区间最后。每次 check 需要做 \(m\) 个操作,操作结束之后如果目标位置的值为 \(1\),就说明答案大于 \(u\),否则小于等于 \(u\)

渐进时间复杂度 \(O((n + m) \log ^2 n )\)

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 100000 + 5;
int n, m, a[MAX_N], b[MAX_N], tree[MAX_N << 2], tag[MAX_N << 2];
int op[MAX_N], opL[MAX_N], opR[MAX_N];
int pos;
void makeTag(int u) {
for (int i = 1; i <= n; ++i) b[i] = (a[i] > u ? 1 : 0);
// printf("u = %d\n", u);
// for (int i = 1; i <= n; ++i) printf("%d%c", b[i], i == n ? '\n' : ' ');
}
inline int ls(int o) {
return o << 1;
}
inline int rs(int o) {
return o << 1 | 1;
}
inline void pushUp(int o) {
tree[o] = tree[ls(o)] + tree[rs(o)];
}
inline void pushDown(int o, int l, int r) {
if (tag[o] == -1) return;
tag[ls(o)] = tag[rs(o)] = tag[o];
int mid = (l + r) >> 1;
tree[ls(o)] = tag[o] * (mid - l + 1);
tree[rs(o)] = tag[o] * (r - mid);
tag[o] = -1;
}
void build(int o, int l, int r) {
tag[o] = -1;
if (l == r) {
tree[o] = b[l];
return;
}
int mid = (l + r) >> 1;
build(ls(o), l, mid);
build(rs(o), mid + 1, r);
pushUp(o);
}
void update(int o, int l, int r, int L, int R, int v) {
if (L <= l && r <= R) {
tag[o] = v;
tree[o] = v * (r - l + 1);
return;
}
int mid = (l + r) >> 1;
pushDown(o, l, r);
if (L <= mid) update(ls(o), l, mid, L, R, v);
if (R > mid) update(rs(o), mid + 1, r, L, R, v);
pushUp(o);
}
int query(int o, int l, int r, int L, int R) {
if (L <= l && r <= R) return tree[o];
int mid = (l + r) >> 1, ret = 0;
pushDown(o, l, r);
if (L <= mid) ret += query(ls(o), l, mid, L, R);
if (R > mid) ret += query(rs(o), mid + 1, r, L, R);
return ret;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", a + i);
for (int i = 1; i <= m; ++i) scanf("%d%d%d", op + i, opL + i, opR + i);
scanf("%d", &pos);
int l = 1, r = n;
while (l < r) {
// printf("l = %d, r = %d\n", l, r);
int mid = (l + r) >> 1;
makeTag(mid);
build(1, 1, n);
for (int i = 1; i <= m; ++i) {
int sum = query(1, 1, n, opL[i], opR[i]);
// printf("sum = %d\n", sum);
switch (op[i]) {
case 0: {
int k = opR[i] - sum + 1;
if (opL[i] <= k - 1) update(1, 1, n, opL[i], k - 1, 0);
if (opR[i] >= k) update(1, 1, n, k, opR[i], 1);
break;
}
case 1: {
int k = opL[i] + sum - 1;
if (opL[i] <= k) update(1, 1, n, opL[i], k, 1);
if (opR[i] >= k + 1) update(1, 1, n, k + 1, opR[i], 0);
break;
}
}
}
if (query(1, 1, n, pos, pos)) l = mid + 1;
else r = mid;
}
printf("%d\n", l);
return 0;
}

题目链接:2019 牛客多校第五场 E

最多 26 个点,\(2^n \approx 6 \times 10^7\),考虑用二进制压缩状态。状态 \(s\) 的第 \(i\) 位表示取或者不取第 \(i\) 个点。

我们用 \(f(s)\) 表示状态 \(s\) 的最大独立集的个数,可以从下面两个状态推得:二进制 \(s\) 的最后一个为1的位置不属于最大独立集 \(f(s) = f(s - {\rm lowbit}(s) )\) 二进制 \(s\) 的最后一个为1的位置属于最大独立集 \(f(s) = f(s - {\rm adj}(u)) + 1\) 其中 \({\rm adj}(u)\) 表示最后一个为 1 的位置和它相邻节点的集合,即 \(v\) 在最大独立集中,则与它邻接的点一定不在最大独立集中。二者取最大即可。

时间复杂度 \(O(2^n)\)

需要特别注意这题空间卡得很紧,需要用 char 来存答案。

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 26;
const int MAX_S = (1 << 26);
int n, m, all;
vector <int> g[MAX_N];
int c[MAX_N];
char f[MAX_S];
char dfs(int s) {
if (f[s] != -1) return f[s];
int u = s, pos = 0;
while (!(u & 1)) ++pos, u >>= 1;
short notInSet = dfs(s - (1 << pos));
short inSet = 1 + dfs(s & c[pos]);
f[s] = max(inSet, notInSet);
return f[s];
}
int main() {
scanf("%d%d", &n, &m);
all = (1 << n) - 1;
int u, v;
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &u, &v);
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 0; i < n; ++i) {
c[i] += (1 << i);
for (auto const &e: g[i]) {
c[i] += (1 << e);
}
c[i] = c[i] ^ all;
// printf("%d>", i), printBit(c[i]), putchar('>'), printBit(c[i] ^ all), puts("");
}
fill(f, f + MAX_S, -1);
f[0] = 0;
LL ans = 0;
for (int i = 0; i <= all; ++i) ans += int(dfs(i));
printf("%lld\n", ans);
return 0;
}

题目链接:2019 牛客多校第五场 B

如果使用高精度每次除以2的操作是 \(O(10^6)\) 的,这里我们需要每次倍增规模让指数规模变小的操作是 \(O(1)\) 的,可以使用以10为单位倍增:

\[ A^b =\left\{  \begin{aligned}  &  [A^{\frac{b}{10}}] ^ {10} , & b \bmod 10 = 0 \\ &  [A^{\frac{b}{10}}] ^ {10} \times A^{b\bmod 10} ,  & b \bmod 10 \neq 0   \end{aligned} \right . \]

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
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAX_N = 1000000 + 5;
LL x[2], a, b, mod;
char n[MAX_N];
struct Matrix {
LL v[2][2];
Matrix(LL lu = 0, LL ru = 0, LL ld = 0, LL rd = 0) {
v[0][0] = lu; v[0][1] = ru; v[1][0] = ld; v[1][1] = rd;
}
inline friend Matrix operator * (const Matrix &l, const Matrix &r) {
Matrix ret;
ret.v[0][0] = ((l.v[0][0] * r.v[0][0]) % mod + (l.v[0][1] * r.v[1][0]) % mod) % mod;
ret.v[0][1] = ((l.v[0][0] * r.v[0][1]) % mod + (l.v[0][1] * r.v[1][1]) % mod) % mod;
ret.v[1][0] = ((l.v[1][0] * r.v[0][0]) % mod + (l.v[1][1] * r.v[1][0]) % mod) % mod;
ret.v[1][1] = ((l.v[1][0] * r.v[0][1]) % mod + (l.v[1][1] * r.v[1][1]) % mod) % mod;
return ret;
}
};
inline Matrix getPowStepTwo(Matrix o, LL y) {
Matrix ret = Matrix(1, 0, 0, 1);
while (y) {
if (y & 1) ret = ret * o;
o = o * o;
y >>= 1;
}
return ret;
}
Matrix getPowStepTen(Matrix o, char *s) {
int len = strlen(s);
Matrix tmp;
Matrix ret = Matrix(1, 0, 0, 1);
for (int i = len - 1; i >= 0; --i) {
int x = s[i] - '0';
if (x) ret = ret * getPowStepTwo(o, x);
// o = getPowStepTwo(o, 10);
tmp = o * o;
tmp = tmp * tmp;
tmp = tmp * tmp;
o = o * o * tmp;
}
return ret;
}
int main() {
scanf("%lld%lld%lld%lld", x, x + 1, &a, &b);
scanf("%s%lld", n, &mod);
Matrix ori = Matrix(a, b, 1, 0);
Matrix ans = getPowStepTen(ori, n);
LL out = ((ans.v[1][0] * x[1]) % mod + (ans.v[1][1] * x[0]) % mod) % mod;
printf("%lld\n", out);
return 0;
}

给出一个序列 \(a_n\) , 求选出四个数并且四个数的最大公约数为1的情况数,根据莫比乌斯反演定理

\[ \begin{aligned} & \sum_{u,v,p,q \in \{a_n\} } [{\rm gcd}(a_u, a_v, a_p, a_q) = 1]  \\ = & \sum_{u,v,p,q \in \{a_n\}}  \sum_{t | d} \mu (t) \end{aligned} \]

其中 \(d = {\rm gcd}(a_u, a_v, a_p, a_q)\),则调换求和次序,上式可化为

\[\sum_{t = 1}^{\max \{ a_n\} } \mu (t) {f(t) \choose 4}\]

其中 \(f(t)\)\(\{a_n\}\)\(t\) 的倍数的个数,求法类似埃筛。那么预处理出莫比乌斯函数的函数值,就可以在 \(O(k \log k)\) 的时间得到答案,其中 $k = { a_n } $。

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

using namespace std;

typedef long long LL;

const int MAX_N = 10000 + 5;
int n, a[MAX_N], h[MAX_N];

namespace LinearSieve {
bool vis[MAX_N];
int mu[MAX_N], p[MAX_N], tot;
void run() {
mu[1] = 1;
vis[0] = vis[1] = 1;
for (int i = 2; i < MAX_N; ++i) {
if (!vis[i]) {
p[++tot] = i;
mu[i] = -1;
}
for (int j = 1; j <= tot && LL(i) * p[j] < MAX_N; ++j) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) break;
else mu[i * p[j]] -= mu[i];
}
}
}
};

LL getComb(LL x) {
if (x < 4) return 0;
return x * (x - 1) * (x - 2) * (x - 3) / 24;
}

int main() {
LinearSieve::run();
while (scanf("%d", &n) != EOF) {
memset(h, 0, sizeof h);
int maxNum = -1;
for (int i = 1; i <= n; ++i) scanf("%d", a + i), ++h[a[i]], maxNum = max(maxNum, a[i]);
LL ans = 0;
for (int t = 1; t <= maxNum; ++t) {
LL sum = 0;
for (int u = t; u <= maxNum; u += t) {
sum += h[u];
}
ans += LinearSieve::mu[t] * getComb(sum);
}
printf("%lld\n", ans);
}
return 0;
}

静态区间第K大问题是主席树的经典应用,这里参考洛谷3834(不带修改的主席树)。

本文是博主的学习笔记,不是教程,如读者希望寻找教程,请移步其他博客。

原理

主席树是一种值域线段树,即每个节点 \([x_l,x_r]\) 存的是当前出现的区间 \([l,r]\) 中的数的个数。一般情况下,值域我们先要进行离散化,因为它往往范围很大,那么这里的 \(x_i\) 就是 \(i\) 离散化之后的值。那么主席树中的叶子节点 \([x_u, x_u]\) 就存的是当前阶段 \(u\) 出现的个数。主席树是一种可持久化线段树。之所以说它可持久化是因为它可以保留线段树中每个节点的历史版本,这也是解决静态区间第 K 大问题的一个关键。当我们试图做单点修改的时候,影响到的是从这个点向上走到根节点的这条链,也就是说如果我们要保存这个版本的线段树,只需要新建一条链出来,让这条链上的没有动的左子树指针和右子树指针依旧指向原来的地方,保存当前状态新的根节点。解决静态区间第K大问题的方法是,将所有的 \([1,i]\) 的子区间(一共 \(n\) 个)看成是 \(n\) 个阶段,然后对于这 \(n\) 个阶段去更新线段树,每次会出现一个新的根节点。那么我们在询问区间\([l,r]\)的区间第K大的时候,实际上就是拿\(r\)状态的线段树和 \(l-1\) 状态的线段树相减,得到 \([l,r]\) 之间的值域中每个值出现的次数。于传统线段树相比,主席树的实现需要动态开点,而传统线段树只需要利用堆式存储即可。传统线段树一般开 \(4n\) 倍的空间(当然实际上可以更少),而主席树考虑到对于 \(n\) 个点就有 \(n\) 个阶段,对于第 \(0\) 阶段,需要 \(4n\) 的空间建立传统线段树,对于阶段 \(i \in [1,n]\),每次需要一条链的空间,即线段树的层数 \(\log_2 n\),也就是我们需要 \(n \log_2 n + 4 n\) 的空间。

实现

建树

建树操作只有在第 \(0\) 状态的时候才会使用到,这个时候值域里没有任何点,那么当前每个点的值都为 0,然后动态开点建一颗传统线段树即可。

更新

\(i\) 状态到 \(i+1\) 状态需要更新线段树(意义是把 \(a_{i+1}\) 添加到值域当中),那么我们在更新后面状态的时候,会把前面的状态传参传到update函数中,一开始先复制前状态,然后根据这个值和当前枚举的值域中点的大小关系修改。

查询

对于区间 \([l,r]\),查询状态 \(l-1\)\(r\),然后相减,这里利用了前缀和思想。如果说左子树相减的结果(状态区间 \([l,r]\) 中新增的点在每个区间节点的个数)大于等于 K,那么说明第 K 大在左边找,否则如果当前左子树大小为 \(s\),则在右边找第 \(k-s\) 大的数,这里的查询结果是离散化完之后第 K 大数的值。

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

using namespace std;

typedef long long LL;

const int MAX_N = 200000 + 5;
int n, m, a[MAX_N], b[MAX_N], tot, root[MAX_N];
int cnt, tree[MAX_N * 40], lson[MAX_N * 40], rson[MAX_N * 40];

int build(int l, int r) {
int o = ++cnt;
tree[o] = 0;
if (l < r) {
int mid = (l + r) >> 1;
lson[o] = build(l, mid);
rson[o] = build(mid + 1, r);
}
return o;
}

int update(int pre, int l, int r, int pos) {
int o = ++cnt;
lson[o] = lson[pre]; rson[o] = rson[pre]; tree[o] = tree[pre] + 1;
if (l < r) {
int mid = (l + r) >> 1;
if (pos <= mid) lson[o] = update(lson[pre], l, mid, pos);
else rson[o] = update(rson[pre], mid + 1, r, pos);
}
return o;
}

int query(int bef, int aft, int l, int r, int k) {
if (l == r) return l;
int x = tree[lson[aft]] - tree[lson[bef]];
int mid = (l + r) >> 1;
if (x >= k) return query(lson[bef], lson[aft], l, mid, k);
else return query(rson[bef], rson[aft], mid + 1, r, k - x);
}

inline int getId(int u) {
return lower_bound(b + 1, b + tot + 1, u) - b;
}

int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", a + i), b[i] = a[i];
sort(b + 1, b + n + 1);
tot = unique(b + 1, b + n + 1) - b - 1;
root[0] = build(1, tot);
for (int i = 1; i <= n; ++i) {
root[i] = update(root[i - 1], 1, tot, getId(a[i]));
}

int l, r, k;
for (int i = 1; i <= m; ++i) {
scanf("%d%d%d", &l, &r, &k);
printf("%d\n", b[query(root[l - 1], root[r], 1, tot, k)]);
}

return 0;
}