日记 - 伊埃斯的博客站

谁家好人六一还上课啊？

我们发现这玩意有两维： $q$ 和 $n$ 。我们可以通过扫描线去掉 $n$ 这一维。那么问题就变成了这样：将询问离线。对于每个点，有 $114514$ 个操作，分别是：往里面加一个数或者查询当前的 $k$ 小值。

显然如果只有一个点，就是一个权值线段树裸题，但是我们有扫描线，不能让操作维持原来的顺序了。由于每次插入的点都不一样，我们在叶子节点维护一个时间戳。每次查询时间戳小于当前查询的时间戳的 $k$ 小值就行。因为插入的数是严格单增的，所以正确性显然。

我们掏一个样例出来：

\frac{314}{100} < \frac{p}{q} < \frac{315}{100}

然后来推式子：

\frac{314}{100} < \frac{p}{q} < \frac{315}{100} \\ \frac{14}{100} < \frac{p - 3q}{q} < \frac{15}{100}

设 $r = p - 3q$ ：

\frac{14}{100} < \frac{r}{q} < \frac{15}{100} \\ \frac{100}{14} < \frac{q}{r} < \frac{100}{15}

我们发现又回去了。简而言之就是这样：

那有人要问了：一边真分数一边假分数怎么办？显然这时的 $q = p = 1$ 。

我们对于每个操作 $x,y,z$ ，我们建一个新的 $z'$ ，由它向当前 $'$ 最多的 $x,y$ 建边。如果当前已经有 $z'$ 就新建一个 $z''$ 。于是我们得到了一个有向无环图。每个点都有一个点权，对于 $i \in [1,n]$ ， $'$ 最多的那个点的点权就是 $b_i$ 。

由于是有向无环图，我们可以拓扑排序。我们建的边其实表示一种限制关系： $u < v$ 的时候才有 $u \to v$ 。用 $a_u$ 表示 $u$ 的点权，那么对于每条边就是 $a_v = \max(a_u,a_v)$ 。最后的答案就是 $\{a_i | i \in [1,n]\}$ 。

判无解就是拿答案推一遍就是了。

指尖在键盘上跃动，青轴奏出悦耳和鸣。

我还能坚持多久呢？

Thanks for reading!

周日 6月 01 2025

532 字 · 2 分钟