传送门 首先考虑 S u b t a s k 3 Subtask\ 3 Subtask 3，这些点是单调的，所以用线段树维护区间赋值 S u b t a s k 4 Subtask\ 4 Subtask 4，没有插入，考虑如果一个点被推到一个地方，那么它与其它的相对顺序就不会变，所以我们用动态开点线段树来找点，用一个平衡树来维护被推的点，平衡树支持插入，区间赋值 对于有插入的情况，即对

传送门 建出笛卡尔树，假设当前处理 [ l , r ] [l,r] [l,r]，高于最大值的星星只能保留一个 一颗星星可以定位到上述的唯一一个区间，所以我们可以枚举这一棵星星 选了这颗星星的话会 b a n ban ban 掉一些区间的星星，而这个在笛卡尔树上是一条链 如果令 f , g f,g f,g 表示当前区间不选 / 选星星，那么 b a n ban ban 掉的就是强制不选星星

传送门 O ( n 2 ) O(n^2) O(n2) 做法：两两查询一次，那么给颜色数为 1 的数对连边，那么一个点可以连出 1 或 3 条边 对于一条的可以直接确定，对于 3 条的，假设当前位 i i i，它喜欢的为 x x x，喜欢它的为 y y y，颜色相同的为 z z z，那么当且仅当查询 ( i , y , z ) (i,y,z) (i,y,z) 时为 1，如果我们给 (

传送门 唯一能自己做出来的一道（呜呜呜）暴力做法是考虑 d p dp dp 出 f 0 / 1 , x , y f_{0/1,x,y} f0/1,x,y​ 表示最后一个在 A / B A/B A/B， A , B A,B A,B 选了 x , y x,y x,y 合不合法，那么发现对于某个特定的 x + y x+y x+y，合法的 x x x 是一个区间，所以记录左右端点 O (

Description 在河狸国，一条路上有 N N N 座城市，依次编为 1 … N 1\ldots N 1…N 号；连接城市 i i i 和城市 i + 1 i+1 i+1 的那段路被称为 i i i 号路。在河狸国，一天有 1 0 9 10^9 109 秒，依次称为时刻 0 … 1 0 9 − 1 0\ldots 10^9-1 0…109−1。从城市 i i i 沿路到达与