CF666E Forensic Examination
CodeforcesLuogu分析先对 $T_{1..m}$ 建立广义 SAM，然后把 $S$ 丢上去匹配，记录每个前缀匹配到的节点 $pos_i$。考虑对每个节点维护一棵以 $T$ 的下标为下标的线段树，线段树上的每个节点维护当前串在这些 $T$ 串中的出现次数的最大值及其下标。这可以通过线段树合并预处理出来。询问时，我们首先找到 $s_{l..r}$ 所在的节点，直接从 $pos_r$ ...
标签 线段树 下的文章
- 首页
- 线段树
洛谷4428 [BJOI2018]二进制
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$ 的倍数。如果 ...
洛谷5324 [BJOI2019]删数
LuoguLOJ分析可以发现一个事情：我们把每个值的出现次数看成这个值对应的一根“柱子”的高度，然后把所有柱子向左推倒，那么最少需要修改的数的个数即为 $[1,n]$ 中未被柱子覆盖的数的个数。于是可以直接用线段树维护，区间平移维护平移标记即可。在平移时两侧的柱子可能会进来、出去，需要及时加入和去除掉。代码// ==================================== // ...
洛谷4364 [九省联考2018]IIIDX
LuoguLOJ分析先考虑一个贪心。我们把 $d_i$ 从大到小排序，那么每个子树都对应一段区间，我们把儿子按照编号排序，然后把区间依次划分下去即可。这样子只能通过所有 $d_i$ 互不相同的点，原因是在 $d_i$ 相同时可以通过一些交换使得编号小的点的 $d_i$ 变大。考虑修正这个贪心。我们维护 $c_i$ 表示 $\leq d_i$ 的可用的难度的个数，那么节点 $u$ 只能选择 $...
洛谷4384 [八省联考2018]制胡窜
LuoguLOJ分析首先容斥一下，求出三段都不包含 $s_{l..r}$ 的方案数，然后用 ${n-1\choose 2}$ 减掉即为答案。我们先把所有和 $s_{l..r}$ 相等的子串位置都找到，然后分类讨论一下：如果有三个互不相交的串，方案数是 $0$。如果最左边的串和最右边的串相交：考虑 $i$ 的位置：如果 $i\in[1,l_1)$，那么 $j\in(l_m,r_1]$，方案数为...
洛谷4365 [九省联考2018]秘密袭击coat
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...
洛谷4747 [CERC2017]Intrinsic Interval
LuoguGym分析析合树模板题。如果两个点在析合树上的 LCA 是析点，那么答案就是这个析点对应的段；否则还要找到两个点所在的两棵子树，LCA 的儿子序列中这两个子树间的子序列才是答案。代码// ==================================== // author: M_sea // website: https://m-sea-blog.com/ // =...
洛谷5607 [Ynoi2013]无力回天NOI2017
Luogu分析没想到差分 /ll根据要求的东西，不难想到线性基。现在既然有一个区间询问，而且线性基还很好合并，那么可以想到在外面套一层线段树。问题是区间修改时一个线性基如何整体异或一个值。考虑差分，变成单点修改，直接把叶节点线性基清空然后 pushup 上去即可。可以证明 $a_{l..r}$ 的线性基和 $a_l\cup(a_i-a_{i-1})_{l+1..r}$ 的线性基是相同的，所以...
JOISC2019 简要题解
官网AtCoderLOJ試験 / Examination三维偏序板子，CDQ 即可。代码ビーバーの会合 / Meetings首先有一个结论：Query(x,y,z) 返回的是三个点两两之间 LCA 中最深的那个。我们先在 $[1,n)$ 中随机一个点 $y$，然后询问 $(0,y,z)$，即可求出 $0\to y$ 链上的点以及其它点在链上那个点的子树中。那么直接递归处理链上每个点剩下的子树...
LOJ576 「LibreOJ NOI Round #2」签到游戏
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$ 满...