日记

谁家好人六一还上课啊？

混凝土粉末# Link to

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

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

A/B < p/q < C/D# Link to

我们掏一个样例出来：

然后来推式子：

设 $r = p - 3q$：

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

• 两边都是真分数：仨一同取反。
• 两边都是假分数：把一边变成真分数。

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

Gellyfish and Camellia Japonica# Link to

我们对于每个操作 $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]\}$。

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

后日谈 # Link to 后日谈

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

我还能坚持多久呢？