二分答案

晚了几天写，暴力场 $\text{score：40 + 40 + 45 = 125 rk：17/30}$ Problem A：Tree题目描述 数据范围对 $100\%$ 的数据，$1 \le n \le 10^8, ~ 1000 \le k \le 10^8$ 题解很容易发现，满足条件等价于要求树中没有任意一条从根出发的路径经过超过 $k - 1$ 个左儿子 然后就是一个很妙的转换，将树按如下规则变为括号序列： 子树 $u$ 括号序 = ‘(‘ + ‘$u$ 左子树括号序’ + ‘)’ + ‘$u$ 右子树括号序 给个题解的图例 实际上可以不用考虑叶节点，那么现在将 $n$ 变为 $n - 1$，$k$ 变为 $k - 2$ 那么现在的任务就变为在坐标系中将左括号看作往右上角走，右括号看作往右下角走，从 $(0, 0)$ 最终走到 $(2n, 0)$ 的方案数，并需要满足过程中纵坐标始终在 $[0, k]$ 中的方案数（注意此时 $n, k$ 已变化） 这就是类似卡特兰数，但是有两条限制，即不能碰到 $y = - 1$ 也不能碰到 $y = k + 1$ 又从 $(x1, y1 ...

题目描述有 $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$ 题解很显然所有人一定会不断向拿烟花的人靠近 可以发现，一个拿烟花棒的人和另一个人相遇时，让另一个人跟着拿烟花的人走直至烟花在灭掉的瞬间将烟花传递的情况和在相遇时传递时一样的（注意相对位置， ...

一道其实很简单然而我还是瞄了题解的题 首先考虑二分答案 显然将小于 $mid$ 的赋为 $-1$，将大于等于 $mid$ 赋为 $1$ 那么显然 $total = $ $[q_1, q_2]$ 最长后缀 $+$ 中间必选 $+$ $[q_3, q_4]$ 最长前缀 然后若 $total \ge 0$ 则 $check (mid)$ 返回 $true$ 很好然后我就不会处理了 于是题解就说将每个 $mid$ 建一棵线段树，然后用主席树就不会 $MLE$（好吧原来本来是想建序列上的主席树的说当然并不可行 那么每次 $check$ 就在 $mid$ 号版本上的树查询即可 代码1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061 ...