CodeforcesLuogu分析先对 $T_{1..m}$ 建立广义 SAM,然后把 $S$ 丢上去匹配,记录每个前缀匹配到的节点 $pos_i$。考虑对每个节点维护一棵以 $T$ 的下标为下标的线段树,线段树上的每个节点维护当前串在这些 $T$ 串中的出现次数的最大值及其下标。这可以通过线段树合并预处理出来。询问时,我们首先找到 $s_{l..r}$ 所在的节点,直接从 $pos_r$ ...
LuoguLOJ分析二进制下每一位模 $3$ 的余数是 $1,2,1,2,\cdots$,也可以看成 $1,-1,1,-1,\cdots$。假设有 $k$ 个 $1$,我们要将其分配到 $\lceil\frac{n}{2}\rceil$ 个 $1$ 和 $\lfloor\frac{n}{2}\rfloor$ 个 $-1$ 上,使得分配到的 $1$ 和 $-1$ 的和是 $3$ 的倍数。如果 ...
LuoguLOJ分析可以发现一个事情:我们把每个值的出现次数看成这个值对应的一根“柱子”的高度,然后把所有柱子向左推倒,那么最少需要修改的数的个数即为 $[1,n]$ 中未被柱子覆盖的数的个数。于是可以直接用线段树维护,区间平移维护平移标记即可。在平移时两侧的柱子可能会进来、出去,需要及时加入和去除掉。代码// ==================================== // ...
LuoguLOJ分析先考虑一个贪心。我们把 $d_i$ 从大到小排序,那么每个子树都对应一段区间,我们把儿子按照编号排序,然后把区间依次划分下去即可。这样子只能通过所有 $d_i$ 互不相同的点,原因是在 $d_i$ 相同时可以通过一些交换使得编号小的点的 $d_i$ 变大。考虑修正这个贪心。我们维护 $c_i$ 表示 $\leq d_i$ 的可用的难度的个数,那么节点 $u$ 只能选择 $...
LuoguLOJ分析首先容斥一下,求出三段都不包含 $s_{l..r}$ 的方案数,然后用 ${n-1\choose 2}$ 减掉即为答案。我们先把所有和 $s_{l..r}$ 相等的子串位置都找到,然后分类讨论一下:如果有三个互不相交的串,方案数是 $0$。如果最左边的串和最右边的串相交:考虑 $i$ 的位置:如果 $i\in[1,l_1)$,那么 $j\in(l_m,r_1]$,方案数为...
LuoguLOJ分析首先把第 $k$ 大转化掉:不妨再设一个 $g_{i,j,k}$ 表示子树 $f_{i,j,k}$ 的和,并设 $G_{i,j}(x)=\sum_k g_{i,j,k}x^k$。答案即为 $\sum_{i=k}^n[x^i](\sum_j G_{1,j})$。看起来这个转移并没有什么可以优化的地方。但是 $F_{i,j}$ 和 $G_{i,j}$ 的最高次项都是 $x^n...
LuoguGym分析析合树模板题。如果两个点在析合树上的 LCA 是析点,那么答案就是这个析点对应的段;否则还要找到两个点所在的两棵子树,LCA 的儿子序列中这两个子树间的子序列才是答案。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =...
Luogu分析没想到差分 /ll根据要求的东西,不难想到线性基。现在既然有一个区间询问,而且线性基还很好合并,那么可以想到在外面套一层线段树。问题是区间修改时一个线性基如何整体异或一个值。考虑差分,变成单点修改,直接把叶节点线性基清空然后 pushup 上去即可。可以证明 $a_{l..r}$ 的线性基和 $a_l\cup(a_i-a_{i-1})_{l+1..r}$ 的线性基是相同的,所以...
官网AtCoderLOJ試験 / Examination三维偏序板子,CDQ 即可。代码ビーバーの会合 / Meetings首先有一个结论:Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。我们先在 $[1,n)$ 中随机一个点 $y$,然后询问 $(0,y,z)$,即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。那么直接递归处理链上每个点剩下的子树...
LOJ分析设 $s_i$ 为 $\sum_{j=1}^i b_j$,则一次询问可以确定 $s_r-s_{l-1}$。如果我们看成连边 $(l-1,r)$,则相当于要让 $(0,n)$ 连通,也就是要求最小生成树。根据 Kruskal 那套理论,我们一定会连边 $(0,n)$。根据 Prim 那套理论,剩下的点要么连 $(0,i)$,要么连 $(i,n)$。更具体的,一定存在一个点 $p$ 满...