有 $N$ 个位置， $M$ 个操作。

操作有两种：

• 如果是 1 a b c 的形式表示在第 $a$ 个位置到第 $b$ 个位置，每个位置加入一个数 $c$ ；
• 如果是 2 a b c 形式，表示询问从第 $a$ 个位置到第 $b$ 个位置，第 $c$ 大的数是多少。

有 $n$ 朵花,每朵花有三个属性：花形( $s$ )、颜色( $c$ )、气味( $m$ )，用三个整数表示。显然，两朵花可能有同样的属性。

定义一朵花 $A$ 比另一朵花 $B$ 要美丽，当且仅当 $S_a\geq S_b$ , $C_a\geq C_b$ , $M_a \geq M_b$ 。定义一朵花的等级是它拥有的美丽能超过的花的数量。

求出每个等级的花的数量。

对于一棵树，我们可以将某条链和与该链相连的边抽出来，称其为一个“毛毛虫”。求在这个树中点数最多的毛毛虫的点数。

$n < 300000$

青春真的是一个非常空泛而又令人迷茫的词汇。

给出一个 $n$ 个节点的有根树。有 $q$ 次询问，每次询问给出 $l,r,z$ ，求 $\sum _ {l \leq i \leq r}dep[LCA(i,z)]$ 。

维护一个动态的关于 $x$的无穷多项式 ，这个多项式初始时对于所有 $i$ 有 $a_i = 0$

操作者可以进行四种操作：

• mul L R V 表示将 $x^L$ 到 $x^R$ 这些项的系数乘上某个定值 $v$ ；

• add L R V 表示将 $x^L$ 到 $x^R$ 这些项的系数加上某个定值 $v$ ；

• mulx L R 表示将 $x^L$ 到 $x^R$ 这些项乘上x变量；

• query V 求 $f(v)$ 的值。

操作集中在前三种，第四种操作不会出现超过 $10$ 次。

给定一棵 $n$ 个节点的树，对于每个点都有两个权值 $w_i,c_i$ 。

存在 $m$ 个操作，分为4类。

• “CC x c”：将 $c_x$ 更改为 $c$ ；

• “CW x w”：将 $w_x$ 更改为 $w$ ；

• “QS x y”：对所有满足在 $x$ 到 $y$ 路径上且 $c_i = c_x = c_y$ 的节点 $i$，求 $\sum w_i$ ；

• “QM x y”：对所有满足在 $x$ 到 $y$ 路径上且 $c_i = c_x = c_y$ 的节点 $i$ ，求 $\max(w_i)$ ；

对于后两个操作，保证 $c_x = c_y$ 。

可持久化线段树，是一种可以进行可持久化操作的线段树，具有优越的时间复杂度。

某个国家有 $n$ 个城市，这 $n$ 个点之间的边构成一棵树。

现求一条边长度和不超过 $S$ 的路径（两端都是城市，可以只为一个城市），使得所有城市到这条路径的距离的最大值最小，并输出这个最小值。

小Z有一片森林，含有 $N$ 个节点，每个节点上都有一个非负整数作为权值。初始的时候，森林中有 $M$ 条边。

小Z希望执行 $T$ 个操作，操作有两类：

• Q x y k 查询点 $x$ 到点 $y$ 路径上所有的权值中，第 $k$ 小的权值是多少。此操作保证点 $x$ 和点 $y$ 连通，同时这两个节点的路径上至少有 $k$ 个点。

• L x y 在点 $x$ 和点 $y$ 之间连接一条边。保证完成此操作后，仍然是一片森林。

强制在线。

对于所有的数据 $n,m,T \leq 8 \times 10^4$ 。