线段树

今日依旧三道集训队原题，无部分分，连续三次 真该问候搬题人他母亲大人 $\text{score：NULL rk：NULL}$ Problem A：Sasha And CirclesProblem B：Choosing Ads题目描述给定一个长度为 $n$ 的序列和一个整数 $p$。 有 $m$ 个操作，操作要么是区间赋值，要么是询问区间内出现次数至少占 $p\%$ 的数。 输出询问的答案时，可以包含错的数，也可以重复输出，但对的数一定要在答案中，且输出的数的个数不超过 $\lfloor \frac{100}p \rfloor$ 数据范围对 $100\%$ 的数据，$n, m \le 1.5 \times 10^5, ~ 20 \le p \le 100$ 题解先考虑 $p = 51$ 的情况，很明显就是求区间众数 有一个经典区间众数套路，给数字 $i$ 一个数组 $c_i$，设当前众数 $p$，每次加一个数字 $t$，若该数字等于 $p$，则 $c_p ++$，反之则 $c_p –$，若删前 $c_p = 0$，则 $p = t$，同时 $c_p = 1$ 这样子虽然没有计算每种数 ...

线段树求直径可以求任意子树（包括连子树都不算的分散节点集合）的直径，适用范围广。 线段树的每个节点所对应的区间$[L, R]$，指代了$Dfn$在$[L, R]$内节点，其中线段树上每个节点存储了$diam$（当前区间直径）及$lp, rp$（当前直径对应的左右端点），每次$Merge$操作分为全左区间、全右区间和横跨两个区间作讨论，对于第三种情况，选择两侧原直径端点求$Dist$取最值即可，正确性显然，查询直接通过$Dfn$查询即可。 当然可能有一些区间内的点不连通，先当作它们连通即可。 对于删除某些子树，相当于把整棵树分为$n$部分，查询每个部分，全部$Merge$起来即可。 例题Snow的追寻 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101 ...

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

题目描述$\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$），再将之 ...

前置「Hall定理」 二分图G中的两部分顶点组成的集合分别为X, Y(假设有|X|≤|Y||X|≤|Y|)。G中有一组无公共点的边，一端恰好为组成X的点(也就是存在完美匹配)的充分必要条件是：X中的任意k个点至少与Y中的k个点相邻，即对于X中的一个点集W ，令N(W)为W的所有邻居， 霍尔定理即对于任意W，|W|≤|N(W) 题解由于最坏情况任选 $k$ 个是选一端连续的区间 $[l, r]$，根据Hall定理的 $|W| \le N(W)$ 可以得到$$\begin{aligned}sum[l, r] &\le (r - l + 1 + d) \cdot k \\sum[l, r] - (r - l +1) \cdot k &\le d \cdot k\end{aligned}$$那么就可以在线段树中将每个点的权值设为 $value - k$，然后维护最大子段和 $sumax$ 那么最后 $sumax \le d \cdot k ? TAK : NIE$ 即可 代码1234567891011121314151617181920212223242526272 ...

主要题意求字符串$S$与$T$不同的子串总数 题解先考虑$l = 1, r = |T|$的情况： 因为任意子串为字符串前缀的某些后缀，那么令$Lim[i]$表示$T[1…i]$在$S$上所能匹配的最大长度，$Posi[i]$表示$T$的后缀自动机上的点$i$的$endpos$集合中最靠前的位置，那么答案即为 $$Ans = \sum\limits_{i = 1}^{nodes} \max (0, Len[i] - min (Len[Father[i]], Lim[Posi[i]]))$$ 接下来考虑$l, r$任意的情况： 原来能否在$S$的后缀自动机上往下走的判断依据只有当前节点是否存在$c$边，那么有了$l, r$的限制，就多需要判断向下的这个节点的$endpos$是否有存在于$[l + len, r]$（$len$表示已匹配长度）区间的位置，$endpos$集合用动态开点线段树维护一下就好了 代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051 ...

首先显然要先把原数组重新映射一下，令映射过后的数组为 $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 ...