E - Mancala 2
按照题意模拟区间加和即可，但不能直接差分，因为下一次发放球又要使用新的球数，所以需要用到数据结构。
-
线段树做法
- 比较无脑，就用一颗lazytagSegmentTree实现区间加，单点查。
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
146template<class Info, class Tag>
struct LazySegmentTree {
int n;
std::vector<Info> info;
std::vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
LazySegmentTree(std::vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {
n = init_.size();
info.assign(4 << std::__lg(n), Info());
tag.assign(4 << std::__lg(n), Tag());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v) {
info[p].apply(v);
tag[p].apply(v);
}
void push(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, const Info &v) {
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
push(p);
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r);
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l >= y || r <= x) {
return;
}
if (l >= x && r <= y) {
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m, r, x, y, v);
pull(p);
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 0, n, l, r, v);
}
};
struct Tag {
i64 add = 0;
void apply(Tag t) {
add += t.add;
}
};
struct Info {
i64 x = 0;
int r, l;
Info(){}
Info(i64 _x, int l, int r):x(_x), l(l), r(r){}
void apply(Tag t) {
x += t.add * (r - l);
}
};
Info operator+(Info a, Info b) {
return {a.x + b.x, a.l, b.r};
}
signed main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
int n, m;
std::cin >> n >> m;
std::vector<Info> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i].x; a[i].l = i; a[i].r = i + 1;
}
LazySegmentTree<Info, Tag> T(a);
for (int i = 0, x; i < m; i++) {
std::cin >> x;
i64 now = T.rangeQuery(x, x + 1).x;
T.modify(x, {0, x, x + 1});//先把原来的位置清空
T.rangeApply(0, n, {now / n});//平均发放n轮
int y = x + (now % n);
if (y < n) {
T.rangeApply(x + 1, y + 1, {1});
} else {
T.rangeApply(x + 1, n, {1});
T.rangeApply(0, y - n + 1, {1});
}
}
for (int i = 0; i < n; i++) {std::cout << T.rangeQuery(i, i + 1).x << ' ';}
std::cout << '\n';
return 0;
} -
树状数组维护差分
- 用BIT维护一个差分数组
- 区间加直接用差分来解决
- 单点查再利用树状数组快速查询区间和的性质，对差分数组快速求和。
- 用BIT维护一个差分数组
1 | template<class T> struct BIT { |
F - S = 1
顶点为 ((0, 0), (X, Y)) 和 ((A, B)) 的三角形的面积是 (\frac{\vert AY - BX \vert}{2}) 。因此我们可以认为，在给定整数 (X) 和 (Y) 的情况下，这个问题要求找到一对整数 ((A, B)) ，使得
[\vert AY - BX \vert = 2.
]
我们将解释如何解决这个问题。在这里，我们设 (g = \gcd(X, Y)) .(注： (\gcd(a, b)) 被定义为 (\vert a \vert) 和 (\vert b \vert) 的最大公约数）。
如果 (g) 是 (3) 或更大，那么答案就不存在，因为 (AY - BX) 总是 (g) 的倍数。
如果 (g = 1, 2) ，那么我们总是可以使用一种叫做扩展欧氏算法的算法来求解。扩展欧氏算法是这样一种算法：输入整数对 ((a, b)) ，在 (\mathrm{O}(\log \min(|a|, |b|))) 时间内找到一个整数对 ((x, y)) ，使得 (ax + by = \pm \mathrm{gcd}(a, b)) 。(这里，保证整数对 (x, y) 是满足 (\max(|x|, |y|) \leq \max(|a|, |b|)) 的整数）。
将 ((Y, -X)) 作为扩展欧几里得算法的输入，可以得到一对 ((c, d)) ，即
[cY - dX = \pm g
]
和 (\vert c \vert, \vert d \vert \leq 10^{17}) 作为返回值。我们最初想要的是一对 ((A, B)) ，即 (AY - BX =\pm 2) ，可以通过将 (c) 和 (d) 乘以 (\frac{2}{g}) 得到。这个 ((A, B)) 安全地满足 (\vert A \vert, \vert B \vert \leq 10^{18}) 。
因此，问题已经解决。计算复杂度约为 (\mathrm{O}(\log \min (X, Y))) ，足够快了。
1 | i64 exgcd(i64 a, i64 b, i64 &x, i64 &y) { |