洛谷2605 [ZJOI2010]基站选址
Luogu 分析 设 $dp_{i,j}$ 表示建了 $i$ 个基站，最后一个建在 $j$ 时只考虑 $1\sim j$ 的最小代价。 这样子最后会有一段没有算，所以我们在最后再加一个村庄 $n+1$，然后答案就是所有 $dp_{i,n+1}$ 的最小值。 考虑转移。枚举上一个建站的位置可以得到 这里的 $cost(p,j)$ 表示 $[p,j]$ 中只有 $p$ 和 $j$ 建了基站时会...
标签 线段树 下的文章
- 首页
- 线段树
洛谷5025 [SNOI2017]炸弹
Luogu LOJ 分析 最简单的想法是每个炸弹向能炸到的所有炸弹连一条边，然后统计每个炸弹能到达多少个点。 然而这样子边数是 $O(n^2)$ 级别的。注意到一个炸弹一定是向一段区间连边，那么线段树优化连边即可。 统计的话，注意到每个炸弹能到达的的点一定是一段区间。那么缩点后按拓扑序算一下能到达的最小编号和最大编号就好了。 代码 `// ==========================...
AGC001F Wide Swap
AtCoder Luogu 分析 令 $a_{p_i}=i$。注意到要使 $p$ 的字典序最小，则应使 $a$ 的字典序尽量小。 那么题目变为：给定排列 $a_{1..n}$，如果 $|a_i-a_j|\geq k$ 且 $|i-j|=1$ 则可以交换 $a_i,a_j$，求可能排列中字典序最小的。 注意到如果 $a_i,a_j$ 不可能发生交换（也就是说 $|a_i-a_j|<k$）...
CF718C Sasha and Array
Codeforces Luogu 分析 考虑怎么用矩阵求出斐波那契数列的。有 为了方便，下面设 $Q=\begin{bmatrix}1&1\\1&0\end{bmatrix}$ 。 考虑使用线段树维护。每个叶子节点维护一个矩阵：若该位置的值为 $i$ ，则维护的矩阵为 $Q^{i-1}$ 。 注意到矩阵乘法是满足分配律的，那么我们只需要求 $[l,r]$ 内所有维护的矩阵的...
SPOJ GSS 系列简要题解
GSS1 线段树上维护以下 $4$ 个东西： 区间和 区间最大前缀和 区间最大后缀和 区间最大子段和 合并两个区间应该比较简单，这里不再赘述。 GSS2 这题就很神仙了。 把所有询问离线并按右端点排序，然后从左往右扫。 对于线段树的每个叶子节点 $[i,i]$，假设当前扫到了 $p$ ，那么该节点存的是 $\displaystyle\sum_{j=i}^pa_j$ 。 设 $pre_i...
洛谷4065 [JXOI2017]颜色
Luogu 分析 首先发现，两个不同的连续区间对应两个不同的删除方案。 那么就可以统计合法区间的数量。 枚举右端点 $r$ ，考虑左端点 $l$ 怎么样才合法。 设颜色 $k$ 最右边的出现位置为 $max[k]$ ，最左边的出现位置为 $min[k]$ 。 显然所有 $max[k]$大于 $r$ 的颜色都会被删去，所以有在 $(l,r)$ 中不存在一定会被删去的颜色。 也就是要找到一个 $...
洛谷4145 上帝造题的七分钟2 / 花神游历各国
Luogu 分析 题意即维护一个数列，支持区间开平方（取下整）和区间求和。 容易发现，对于最大的数据 $10^{12}$，开 $6$ 次方即可得到 $1$，之后再开方就不会变。 那么对于线段树的每个节点维护一个标记，表示该节点对应的区间是否全为 $1$ 或 $0$。 修改时如果修改到一个满足条件的区间，则不用修改；否则往下递归修改直到到达叶节点或者满足条件的节点。这样子复杂度是对的。 注意可...