思维

给定一个 $n$ 个点的竞赛图，给该图的每条边染色，颜色数量不能超过 $m$ 个，一个染色合法当且仅当不存在长度为 $2$ 的路径，即对有向图中任意路径 $i \rightarrow j \rightarrow k$ 均有边 $i \rightarrow j$ 和边 $j \rightarrow k$ 颜色不同 $2 \le n \le 3000, ~ 2 \le m \le 26$ 设该竞赛图点集 $V$ 考虑染每一种颜色意味着什么，相当于选择一个点集 $S \subseteq V$，将所有边 $(u, v)$ 满足 $u \in S \cap v \in \complement_VS$ 染上该颜色，也就是说我们要找到至多 $m$ 个这样的集合来覆盖所有的边 这样可以给出一个 $m = 2\log n$ 的染色方案，对所有点分治，每次一分为二，给 $S, \complement_V S$ 之间的边按两种方向染上不同的颜色，这样总共需要颜色是 $2\log n$ 的 但实际上可以用二进制来表示这种是否在每个 $S$ 中的关系，对每个 $S_i$，若当前点 $u$ 得到的二进制位 ...

题目描述有 $N$ 人站在一条数轴上。他们人手一个烟花，每人手中的烟花都恰好能燃烧 $T$ 秒。每个烟花只能被点燃一次。$1$ 号站在原点，$i$ 号 $(1 \le i \le N)$ 到 $1$ 号的距离为 $X_i$。保证 $X_1 = 0$，$X_1, X_2, …, X_N$ 单调递增（可能有人位置重叠）开始时，$K$ 号的烟花刚开始燃烧，其他人的烟花均未点燃。他们的点火工具坏了，只能用燃着的烟花将未点燃的烟花点燃。当两人位置重叠且其中一人手中的烟花燃着时，另一人手中的烟花就可以被点燃。忽略点火所需时间。求至少需要以多快的速度跑，才能点燃所有人的烟花（此时可能有些人的烟花已经熄灭了）。速度必须是一个非负整数 数据范围对 $100\%$ 的数据，$1 \le K, N \le 10^5, ~ 1 \le T \le 10^9, ~ 0 \le X_i \le 10^9, ~ X_1 = 0$ 题解很显然所有人一定会不断向拿烟花的人靠近 可以发现，一个拿烟花棒的人和另一个人相遇时，让另一个人跟着拿烟花的人走直至烟花在灭掉的瞬间将烟花传递的情况和在相遇时传递时一样的（注意相对位置， ...

第一次做到这种倍增题，有点有趣 首先区间内的每个点对应相等用并查集维护一下就好了，显然最后的答案就是（并查集个数为 $t$） $9 \cdot 10^{t - 1}$ 当然这样会造成 $O (n^2)$ 的复杂度，那么通过倍增来优化，即将区间二进制拆分，然后每次将 $[l_1, l_1 + 2^k - 1]$ 与 $[l_2, l_2 +2^k - 1]$ 合并，其中 $k$ 为二进制拆分结果所得幂次的部分，那么这样修改就变成 $O (n \log n)$ 了 对于查询，显然是不能直接查询了，那么就通过由大区间到小区间的传递（即将大区间拆分为左右两段，然后分别与之祖先拆分得左右两段合并）来将信息转移到最小的（即以点为单位的）区间段上 那么最后即 $O (n)$ 查询并查集个数即可 故该倍增整体思想即为：将以点为单位处理改为以幂次区间段为单位处理 $\rightarrow$ 将幂次区间段的信息转移到小区间直至单位区间 $\rightarrow$ 答案处理 代码12345678910111213141516171819202122232425262728293031323334353637 ...

首先显然要先把原数组重新映射一下，令映射过后的数组为 $a_i$ 因为题目要求 $|a_j - a_i| >= K$ 的可以置换，那么反之，则有 $|a_j - a_i| < K$ 的 $i, j$ 相对位置不变 故最简单的方法就是对于每个 $i$，将其与所有满足 $|a_j - a_i| < K$ 的 $j$ 连边，然后跑一边拓扑，复杂度 $O (n^2)$ 然后考虑在 $a_i$ 连的这么多边中，若是存在边 $(i, j), (j, k), (i, k)$，其中 $i < j < k$，那么显然 $(i, k)$ 的存在性是无关紧要的 又 $a_i$ 可连边的权值范围是 $(a_i - K, a_i) \cup (a_i, a_i + K)$，那么只需要分别向两个区间中标号最小的那个点连边就好了（单向边，并且一定向标号比自己大的点连），这样就相当于是将原来的乱七八糟连接的图变成了一条条单向的链，并且这些链可以覆盖原来的所有情况 代码1234567891011121314151617181920212223242526272829303132333435 ...