AtCoder Beginner Contest 341
做得太慢了，原因 BC 题意很难懂，而且一开始 AtCoder Better 加载不出来，不好翻译（
先用 10min 做的 AB。其中 B 好几次读错题。
看 C 发现题面这么长压根看不懂，先看小清新 D。
发现一眼出思路，二分很快写完了。后来调二分边界用了很长时间，实际上此时已经过样例了，但由于以前的教训纠结了很长时间。最后还是把右边界开到了 \(10^{18}\)。这时到了 18min。
回来看 C 发现过水，于是用了大量 STL 技巧想秀，结果用时反而更长（
现在是 30min，ABCD 都切了。
看 E，有难度。上午讲课就全讲的可持久化线段树这种题必须手到擒来。
一开始线段树维护的是区间是否好的、区间左右端点的值、区间是否翻转的标记。觉得很好就开始写，最后 build modify 都写完了写到 query 发现不会了，因为当时把线段树复杂度算成 \(\mathcal O(n)\) 的了。放弃之。但实际上这样的复杂度是 \(\mathcal O(\log n)\) 的。
然后回去读题，想到了官方题解的做法，维护异或差分值，甚至这样写都不用懒标记！
写到一半发现需要维护区间翻转。但我不想去改上面的线段树了。于是又写了棵树状数组维护每个节点被翻转的次数。
调了 INF 分钟边界一遍过了。65min 过去了。
然后看 FG。发现貌似都可做，先做题面更简单的 G。几分钟后发现毫无思路。
还是做 F 吧。写了一个拓扑排序结果过了样例 12，但样例 3 跟答案差了 200 左右。调试未遂。赛后发现读错题了。
D - Only one of two
Problem Statement
给你三个正整数 \(n, m, k\)。保证 \(n \ne m\)。
求第 \(k\) 小的正整数满足它能被 \(n, m\) 中的恰好一个数整除。
Solution
首先如果 \(x\) 是答案，即第 \(k\) 小的满足条件的值，那么显然 \(x\) 是满足 \(1 \sim x\) 中有至少 \(k\) 个满足条件的数的最小值。
所以可以二分答案 \(x\)。然后问题转化成了 \(1 \sim x\) 中有多少个数能被 \(n, m\) 中的恰好一个数整除。
首先考虑如果问题是“能被 \(n, m\) 中的任意一个数整除”怎么做。这其实就是经典容斥。
即 \(a\) 表示能被 \(n\) 整除的数量，\(b\) 表示能被 \(m\) 整除的数量，\(c\) 表示能被 \(n\) 整除且能被 \(m\) 整除的数量。那么根据容斥原理，答案为 \(a + b - c\)。
由于 \(n\) 的倍数会在所有正整数中每 \(n\) 个数出现一次，所以不难发现 \(a = \lfloor \frac xn \rfloor, b = \lfloor \frac xm \rfloor\)。
同时，如果一个数被 \(n\) 整除且能被 \(m\) 整数，即这个数是 \(n\) 的倍数也是 \(m\) 的倍数，那么这个数一定是 \(\operatorname{lcm}(n, m)\) 的倍数。
所以有 \(c = \left \lfloor \frac x{\operatorname{lcm}(n, m)} \right \rfloor\)。
那么如果有了”恰好一个数“这个条件，实际上我们只需要将上述答案再减去能被 \(n\) 整除且能被 \(m\) 整除的数量即可。所以答案为：
\[\left \lfloor \frac xn \right \rfloor + \left \lfloor \frac xm \right \rfloor - 2 \times \left \lfloor \frac x{\operatorname{lcm}(n, m)} \right \rfloor \]Code
int n = read(), m = read(), k = read(), res;
int l = 1, r = 1e18, p = n * m / __gcd(n, m);
while (l <= r) {
int mid = l + r >> 1;
if (mid / m + mid / n - mid / p * 2 >= k) res = mid, r = mid - 1;
else l = mid + 1;
}
wel(res);
E - Alternating String
Problem Statement
给定一个长度为 \(n\) 的 \(01\) 字符串 \(s\)。
你需要处理 \(Q\) 次询问：
1 L R：将 \(S\) 中 \(l \sim r\) 的数翻转，即 \(0\) 变 \(1\)，\(1\) 变 \(0\)。2 L R：问 \(S\) 的子串 \(l \sim r\) 是否每两个连续字符都不同。
Solution
我们令 \(a_i = s_i \operatorname{xor} s_{i + 1}\)，即如果 \(s_i = s_{i + 1}\) 则 \(a_i = 0\)，反之为 \(1\)。那么如果区间 \([l, r]\) 满足条件相当于每一个 \(l \le i < r\) 都满足 \(a_i = 1\)，即 \(\sum_{i = l}^{r - 1} a_i = r - l\)。那么询问操作就解决了。
对区间 \([l, r]\) 进行翻转操作，不难发现所有的 \(a_i (l \le i < r)\) 都不会发生变化。发生变化的只有两个边界，即 \(a_{l - 1}\) 和 \(a_r\)，显然这两个值会变成它们相反的数。
所以需要维护一颗单点修改（取反）区间求和的线段树，就做完了。
int n, m;
bool s[N];
struct Tree {
int l, r, s;
}tr[N << 2];
void pushup(int u) {
tr[u].s = tr[ls].s + tr[rs].s;
}
void build(int u, int l, int r) {
tr[u] = {l, r};
if (l == r) tr[u].s = s[l] != s[l + 1];
else {
int mid = l + r >> 1;
build(ls, l, mid), build(rs, mid + 1, r);
pushup(u);
}
return;
}
void modify(int u, int x) {
if (tr[u].l == tr[u].r) tr[u].s ^= 1;
else {
int mid = tr[u].l + tr[u].r >> 1;
if (x <= mid) modify(ls, x);
else modify(rs, x);
pushup(u);
}
}
int query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) return tr[u].s;
int mid = tr[u].l + tr[u].r >> 1, res = 0;
if (l <= mid) res = query(ls, l, r);
if (r > mid) res += query(rs, l, r);
return res;
}
signed main()
{
n = read(), m = read();
fup (i, 1, n) {
char c;
cin >> c;
s[i] = c == '1';
}
if (n == 1) {
while (m -- ) {
int op = read(), l = read(), r = read();
if (op == 2) puts("Yes");
}
return 0;
}
build(1, 1, n - 1);
while (m -- ) {
int op = read(), l = read(), r = read();
if (op == 1) {
if (l != 1) modify(1, l - 1);
if (r != n) modify(1, r);
}
else {
if (l == r || query(1, l, r - 1) == r - l) puts("Yes");
else puts("No");
}
}
return 0;
}