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)$。更具体的，一定存在一个点 $...
标签 线段树 下的文章
- 首页
- 线段树
UOJ515 【UR #19】前进四
UOJ 分析 把所有操作离线，按下标从大到小扫描线，并维护一棵以时间为下标的和后缀 $\min$ 有关的线段树。 那么每个操作相当于对某段时间内取 $\min$，一个位置的后缀最小值个数就是它被取 $\min$ 的次数。 用 Segment Tree Beats 维护即可。 具体的，我们只需要维护最大值、严格次大值和最大值被取 $\min$ 的次数，如果最大值 $\leq$ 要取 $\min...
CF997E Good Subsegments
Codeforces 分析 考虑一个好区间实际上是 $\max-\min=r-l$。 把所有询问按右端点排序，然后扫描线，则我们需要维护每个左端点到右端点的信息。 考虑每个左端点维护 $(\max-\min)-(r-l)$，显然这个东西是 $\geq 0$ 的，所以我们只需要维护最小值出现次数即可，可以用线段树维护。在右移右端点时需要更新信息，用单调栈维护最值即可。 但是我们要求的是所有区间...
AGC028E High Elements
AtCoder 分析 因为要字典序最小，所以可以贪心，从前往后确定所有位，每位尽量填 $0$。 为了方便，我们把是 $p$ 中的前缀最大值的前缀最大值称作“旧的“，不是 $p$ 中前缀最大值的前缀最大值称作”新的“。 首先有一个结论：如果一个 $s$ 合法，那么 $x,y$ 两个序列中一定有一个序列的前缀最大值全都是旧的。 证明可以这样考虑：如果 $x,y$ 中都有一个新的前缀最大值，那么我...
洛谷6773 [NOI2020]命运
Luogu LOJ 分析 规定根节点的深度为 $1$。 考虑 DP。设 $dp_{u,i}$ 表示以 $u$ 为根的子树，下端在子树中的未被覆盖的链的上端的最深深度为 $i$ 时的方案数（$i=0$ 表示全部被覆盖）。这个“最深”的好处在于我们覆盖了深的就一定会覆盖浅的，便于计数。 考虑转移，每次把一棵子树合并进来，考虑子树的父边填 $1$ 还是 $0$ 可以得到 可以想到整体 DP，用线...
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
CF932F Escape Through Leaf
Codeforces Luogu 分析 容易想到一个 DP。设 $dp_u$ 表示 $u$ 跳到叶子节点的最小花费，显然有转移 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。因此可以考虑李超线段树，转移时直接查询对应位置的最小值，然后向上合并即可。 可以看成若干条直线 $y_v=b_v\times x+dp_v$ 在 $a_u$ 处的最小值。...
LOJ535 「LibreOJ Round #6」花火
LOJ 分析 如果只能用操作 $1$，根据某个经典结论答案就是逆序对数。于是很容易想到 $\mathcal{O}(n^3\log n)$ 的暴力：枚举操作 $2$ 交换了哪两个位置，然后求逆序对即可。 考虑优化。因为每次只交换了两个位置，所以没有必要整个重新求一遍逆序对。假设交换了 $i$ 和 $j$，原来的逆序对数是 $A$，那么交换后的逆序对数 $A'$ 为 讨论一下：当 $p_i&l...
洛谷5891 Fracture Ray
Luogu 分析 对于每个数 $x$ 从 $x+\operatorname{count}(x)$ 向 $x$ 连边，则应该是一个森林。为了方便我们再建一个点向每棵树的根连边。 然而点数是 $2^{30}$ 级别的，所以并不能直接拿树剖+线段树搞。 但实际上只有 $2\times 10^5$ 个操作，所以可以考虑建虚树，并对虚树上的每个点求出 $cnt_x$ 表示向上走多少条边能到达虚树上的父...
洛谷4770 [NOI2018]你的名字
Luogu LOJ 分析 先考虑 $l=1,r=|S|$ 的情况。 对 $S$ 和 $T$ 建 SAM。 设 $lim_i$ 表示 $T[1..i]$ 最长的是 $S$ 的子串的后缀的长度，可以在 $S$ 的 SAM 的 Parent 树上跳来求出： 如果有对应的转移直接走过去，匹配长度加 $1$； 否则跳 Parent 树，直到某个点有对应的转移，匹配长度变为该点的 $len$； 如果跳...