A. 操作
题目大意
有一个长为 \(n\) 的、初始全为 \(0\) 的数组和 \(m\) 次操作。操作分两种：
1 l r：将下标区间 \([l, r]\) 内的数全加 \(1\)；
2 l r：将下标区间 \([l, r]\) 内的操作再执行一遍。
求所有操作结束后数组内每个数。
\(1 \leq n, m \leq 1e5\)，保证各操作合法。
思路
简单题。
正着不好搞。考虑将操作倒着来。对操作、数组各开一棵线段树表示这个操作被执行了几次，数组上的同理。于是倒序遍历操作，按要求将对应区间加上就好了。
B. 数码
题目大意
定义 \(S(n, k)\) 表示正整数 \(n\) 在 \(k\) 进制下各数位上数的和。
给定 \(n, K, x\)，你需要求出有多少个整数 \(k \in [2, K]\) 满足 \(S(n, k) \leq x\)。
\(1 \leq n \leq 1e12, 1 \leq K, x \leq 1e18\)
思路
发现数据范围十分大，感觉要么根号要么 \(\log\)。于是考虑根号分治。令 \(S = \sqrt n\)，对 \(k\) 分治。小于 \(S\) 的 \(k\) 可以直接暴力判，大于 \(n\) 的 \(k\) 也好搞。接下来发现对于 $S < k < n $ 的 \(k\)，\(n\) 的 \(k\) 进制表示最多只有两位，而第一位又只有根号种情况。然后又可以打表发现第二位构成若干等差数列，于是就可以搞了。
C. 圆环
题目大意
警察正在追捕一名嫌疑人。他所在的城市可以抽象成一个个点的环，点编号 \(0\) 到 \(n\)，从 \(i\) 到 \((i + 1) \bmod n\) 有条无向边。建立起这条无向边需要 \(C_i\) 的代价，即如果不付出 \(C_i\) 代价这条边是不能通行的。
由于精力有限，警察在接下去 \(P\) 天中的第 \(i\) 天只能在点 \(a_i\) 与 \(b_i\) 之间巡逻。因此，警察想知道在保证每对 \(a_i, b_i\) 联通的条件之下，代价之和的最小值。
\(3 \leq n \leq 5e5\) ，\(1 \leq P \leq 1e5\)
思路
首先所有边全部连上一定合法。于是考虑断开一条边，这样任两点间的路径方向就可以确定。然后考虑枚举断开的是哪一条，增量法维护当前所有的路径方向。剩下的就是求动态路径并上的权值和。也就是区间 \(+1/-1\)，全局 \(>0\) 位置的权值和。可以线段树维护。
D. 小学数学
题目大意
有 \(n\) 个水桶，第 \(i\) 个水桶初始有 \(i\) 升水。定义一次两个水桶间的倒水操作：用当前水量较多的水桶向另一水桶倒水，直到另一桶里的水量翻倍。要求构造一种倒水的方案，使得所有操作结束后剩余水量最多的水桶剩的水最多。
思路
玄学题。
显然答案不会是 \(\sum_{i - 1}^ni\)。
定义一个数被吸收：这个数与另一数操作若干次后变成 \(1 / 0\)。
首先可以考虑将所有数都堆到某一个数（称为吸收塔）上。但是可以发现这样行不通，因为有的时候无法把所有数吸收掉。于是考虑将某两个数作为吸收塔将其他所有数吸收掉。
有一个结论：对于任意两水桶，其中一个水量为 \(2\) 的幂次，另一个水量为奇数，则总能进行操作使得这两个水桶中有一个水桶只剩 \(1\) 升水。
这启发我们将 \(1, 2\) 两个水桶作为吸收塔，用 \(a[2]\) 吸收其他所有数，而将 \(a[1]\) 保留为 \(1\)。每次要吸收一个数 \(x\) 的时候先把 \(a[1]\) 变成 \(2\)，然后不断操作 \(a[2], x\) 直到 \(a[2] \ge x\)。然后反复操作 \(a[1], a[2]\)。根据上面的结论，两个数最终总有一个数会变成 \(1\)。于是把 \(a[1]\) 变成 \(1\)，继续吸收 \(x\) 直到吸收完。
这之后 \(a[2]\) 以后的所有数都只会是 \(1\) 或者 \(0\)。于是可以将每两个 \(1\) 合并成一个 \(2\)，然后吸收这个 \(2\)。这样就可以搞掉 \(a[2]\) 后的每对 \(1\)。那么这样之后最多有两个 \(1\) 和一个作为答案的数。可以证明这样已经是最优的。
时间复杂度玄学。
花絮
因为是 \(918\)，所以考试考到一半开始鸣笛。当时教练不在，于是我们都犹豫要不要站起来默哀。机房里的人一半站着，一半坐着，一半如站如坐。最后大家还是都站起来了。但是好像有好多站起来之后继续调代码的（
标签：水桶,所有,吸收塔,leq,20230918,操作,吸收,集训 From： https://www.cnblogs.com/forgotmyhandle/p/18000270