Ynoi 只胡不写

发现我的 Ynoi 还没做过几道，根本不想写。

有区间 $[l, r, tl, t r]$ ，询问 $[ql, q r, qt]$ ，求 $qt$ 时刻是否能选出区间并为 $[ql, q r]$ 。

序列分治。

对于跨过 $mi d$ 的区间，求最多能覆盖 $mi d$ 两边多远，扫时间维，线段树下标 $[l, mi d]$ ，维护右端点的最小值，线段树二分。

检查在两边的区间能不能补上剩下的。扫 $i = l \to mi d$ ，线段树下标时间维，维护右端点最远能覆盖到哪里，区间取 max，弹出 min $< i$ 的询问。

复杂度 $O (n lo g^{2} n)$ 。

询问 $[l, r]$ 求 $l \leq i < j < k \leq k$ 且 $a_{i} < a_{j} < a_{k}$ 的 $(i, j, k)$ 数。

询问 $[l, r]$ 求 $l \leq i < j < k \leq k$ 且 $(a_{i}, a_{j}, a_{k})$ 是能组成三角形的 $min a_{i} + a_{j} + a_{k}$ 。

对 $[l, r]$ 升或降序排序；询问一个前缀有多少个不同值。

强制在线。

仿照颜色段均摊，维护若干个升或降序段。

权值线段树维护每个值出现次数和是否第一次出现，线段树分裂合并。

复杂度 $O (n lo g n)$ 。

树，树边上有一个字符。

将 $x \to y$ 的路径替换为给定的字符串，保证长为 $k$ ；查询 $x \to y$ 路径的字符串与给定字符串的匹配次数。

树剖，枚举轻边直接查询，重链上一共 $O (q k)$ 次修改 $q$ 次询问，离线，维护哈希值。

复杂度 $O (q k lo g n)$ 。

Quartz 4