P4425:[HNOI/AHOI2018]转盘 – 题解

主要思路

第一次做到线段树维护单调栈的题,来写一写博客。

首先这个题求的就是 \(ans = \min_{i \in [n, 2n)} \max_{j \in [i – n + 1, i]} a_j + i – j\),换一下就是 \(ans = (\min_{i \in [1, n)} \max_{j \in [i, i + n – 1]} a_j + i – j) + n – 1\)。

我们可以考虑做 \(B_i = a_i – i\),然后再去做 \(\min\) 值。然而这样复杂度还是很高。我们考虑静态的问题时,发现其实这题可以做到 \(\Theta(n)\),因为这个其实用一个反着的(从右到左)单调栈就行了。

放到动态问题上,可以尝试用线段树去搞搞:合并的时候,先保留右子树的内容,然后尝试在左子树里进行二分,找到队尾即可。

继续阅读P4425:[HNOI/AHOI2018]转盘 – 题解

HNOI 2018 省队集训 Day 1 – 解题报告

A – Tree

这道题粗看需要 Link Cut Tree,其实不然:如果我们仍然在把节点 \(1\) 作为根节点来处理子树信息、放入线段树,之后的询问我们只需要灵活的分类讨论即可。在实根为 \(root\) 时,\(u, v\) 之间的 \(LCA\) 显然是 \(lca(u, v), lca(root, u), lca(root, v)\) 之间深度最大的那一个。而修改权值和查询权值,只需要讨论两种祖先关系和平行关系即可。

继续阅读HNOI 2018 省队集训 Day 1 – 解题报告