ABC424E
- 注意到,若两根木棍长度相同,那么它们被操作的顺序也是相邻的。于是,若两根木棍“来源”相同,那么它们始终在同一“批次”中被操作。例如:\([1] \to [1/2, 1/2] \to [1/4, 1/4, 1/2] \to [1/4, 1/4, 1/4, 1/4]\)。
- 这启发我们,可以用 pq 维护 \((l, c)\),其中 \(l\) 为长度,\(c\) 表示长度为 \(l\) 的木棍共有 \(c\) 根。
ABC424F
- 首先断环为链,发现每根弦可以被看成一个区间 \([a, b]\)。
- 注意到,加入 \([a, b]\) 的充要条件是其不与其他区间形成相交关系,并且对于已经被加入了的区间,它们要么不交要么一个包含另一个。
- 这种“要么不交要么一个包含另一个”的结构和合法括号串是等价的(即将区间左端点记为 \(\texttt (\),右端点记为 \(\texttt )\)),而括号串合法的充要条件是,令 \(1 := \texttt (, -1 := \texttt )\),则这个 \(\pm 1\) 序列的和为 \(0\) 且每一个前缀和都不小于 \(0\)。
- 线段树维护 \((s, m)\),\(s\) 表示和,\(m\) 表示前缀和的最小值。