数据结构

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

（貌似整个代码不能用 $makeroot$ ？是因为是有根树？） 因为是区间操作，所以可以考虑在区间内与区间外的差异 对于操作 $1$ ，可以看作一个生成节点包含了到下一个 $1$ 操作之间长出的节点，那么对于一个操作 $l, r$ ，相当于是在 $l$ 处将当前生成节点及其包含的节点整个移植到它更改后的位置，到 $r + 1$ 时再移植回去，所以可以考虑将一个 $1$ 操作分解为两个操作（一个移植，一个移植回去），故可以将所有操作按端点、时间排序（以及同位置修改操作必定在查询操作前，因为可以先把树建完再查询对结果没有影响），扫描一遍即可 同时，为了方便移植，将每个生成节点看作新建的一个虚点 对于操作 $0$ ，直接在虚点下 $link$ 即可，因为就算已经建了一些对于当前操作不存在的虚点，也不会对答案造成影响 对于操作 $2$ ，无法正面在 $LCT$ 上算出两点的距离，故可考虑差分，得到 $Ans = Sum_x + Sum_y - 2 * Sum_{lca}$ ，其中实点贡献为 $1$ ，虚点贡献为 $0$ 对于求 $LCA$ ，先 $access (y)$ ，再在 $acces ...

题目描述$\text{opt} = 1$ 时，代表把一个区间 $l, r$ 内的所有数都 $\text{xor}$ 上 $v$。 $\text{opt} = 2$ 时， 查询一个区间 $[l, r]$ 内选任意个数（包括 $0$ 个）数 $\text{xor}$ 起来，这个值与 $v$ 的最大 $\text{xor}$ 和是多少。 题解几乎没写过差分，看完这题之后顿时感觉到了差分的强大 首先显然第二个操作需要维护线性基，然后 $O (\log{n})$ 求解 然后因为有 $1$ 操作，所以若是直接维护区间线性基，在计算答案时不知道 $1$ 操作中的 $v$ 在当前答案中被异或上了奇数还是偶数次，故无法求解 但是在单点修改的情景下就不会有上述问题，故现在的问题是如何将区间问题转化为单点问题 于是就需要差分，让每个 $b_{i + 1} = a_{i + 1} ~ \text{xor} ~ a_i$，那么此时 $v$ 的贡献就只作用于 $b_l$ 与 $b_{r + 1}$，可直接单点修改，然后在线段树上同时维护区间线性基，查询时只需查询 $1…l$ 的前缀和（即 $b_l$），再将之 ...