CF487E Tourists
Codeforces Luogu 分析 可以发现，在从 $u$ 走到 $v$ 的过程中如果经过了一个点双联通分量，那么对于其中的每个点都存在一条经过它的路径。因此，我们一定会经过每个点双中权值最小的点。 从而可以想到广义圆方树。对于每个方点，它的权值应为与它相连的圆点中的最小值。这样子查询直接树剖+线段树即可。因为有修改圆点权值的操作，用 std::multiset 维护每个方点相连的圆点的...
标签 线段树 下的文章
- 首页
- 线段树
洛谷3703 [SDOI2017]树点涂色
Luogu LOJ 分析 可以发现每种颜色一定是一条链，则整棵树相当于被剖分成了若干条链。 考虑 LCT 维护，则 1 操作相当于 access(x)，2 操作相当于询问一条路径上的链数，3 操作相当于求子树中到根路径上链数最大的点。 考虑将 2 操作差分，则只需要用一个数据结构维护每个点到根路径的链数，要求支持区间求最大值。 考虑 access(x) 时对每个点到根路径上的链数的影响。对于...
CF1063F String Journey
Codeforces Luogu 分析 为了方便，把串翻转，条件改为「使 $t_{i-1}$ 是 $t_i$ 的真子串」。 可以发现一个性质，即在一定存在一组最优解使得 $|t_i|=i$，因为某个不满足的串删去多的部分一定不会差。 于是可以考虑一个 DP。设 $dp_i$ 表示最后一个串以 $i$ 结尾时最多能选出多少个串。 然而这个似乎没法转移。冷静分析一下可以发现一定有 $dp_{i-...
CF1270H Number of Components
Codeforces Luogu 分析 可以发现一个性质，即连通块一定是连续的一段。证明可以设 $i<k<j$，然后讨论各种情况，并证明无论如何 $k$ 与 $i,j$ 都连通。证起来有些复杂所以此处略去（ 那么我们可以枚举连通块的最右边的点 $p$，如果 $[1,p]$ 与 $[p+1,n]$ 间没有连边即 $\min_{1\leq i\leq p}a_\max_{p+1\le...
CF671C Ultimate Weirdness of an Array
Codeforces Luogu 分析 考虑求出一个 $H_i$ 表示有多少个 $[l,r]$ 满足 $f(l,r)\leq i$，则答案为 考虑快速求 $nxt_i$。考虑从大到小枚举 $i$，在 $i$ 减小时考虑 $nxt$ 的变化。 假设满足 $i|a_j$ 的 $j$ 为 $x_1,x_2,\cdots,x_m$，则 $[l,r]$ 外至多有这些数中的一个。因此 $nxt_{x_...
CF1286D LCC
Codeforces Luogu 分析 容易发现最早碰撞的一定是相邻的两个球。 我们钦定某一对球是最先撞上的以及它们的运动方向，然后考虑 DP。设 $dp_{i,0/1}$ 表示前 $i$ 个球，当前的球往左/往右，且保证最早撞上的是钦定的那一对的概率。转移讨论一下几种情况即可。 这个转移显然可以写成若干个 $2\times 2$ 的矩阵相乘。如果我们把所有方案按时间从小到大排序再枚举，则每...
CF115E Linear Kingdom Races
Codeforces Luogu 分析 考虑 DP。设 $dp_i$ 表示前 $i$ 条道路的最大收益，不难得到转移 这里的 $c(i,j)$ 表示修建 $i$ 到 $j$ 的道路的花费，$w(i,j)$ 表示修建 $i$ 到 $j$ 的道路获得的收益。 考虑用线段树优化，即要求扫到 $i$ 时每个叶结点的值 $j$ 为 $dp_j-c(j+1,i)+w(j+1,i)$。对于一个新的 $i...
CF903G Yet Another Maxflow Problem
Codeforces Luogu 分析 容易发现，至多只会割掉一条 A 边和一条 B 边。我们加边 $(A_0,A_1,0)$ 和 $(B_n,B_{n+1},0)$，然后求 $A_0$ 到 $B_{n+1}$ 的最大流，就可以转化成恰好割掉一条 A 边和一条 B 边的情况了。 设割掉了 $A_i\to A_{i+1}$ 和 $B_j\to B_{j+1}$，则此时的最大流为 显然对于每个...
洛谷4062 [Code+#1]Yazid 的新生舞会
Luogu LOJ 分析 显然每个数作为众数的情况是相互独立的，因此我们考虑枚举众数 $k$，然后计算有多少个区间中 $k$ 的出现次数超过一半。 不妨把等于 $k$ 的数看做 $1$，不等于 $k$ 的数看做 $-1$，那么我们相当于要求有多少个区间的和大于 $0$。这个东西等价于前缀和的逆序对数。 但是直接做的话当 $A_i$ 的数量比较多时显然会 TLE，所以我们需要一些优化。 考虑到...