【NOI 2077】七重嵌套

题目背景

2077 年，OI 选手已经不再满足于“树套树”。出题人决定把七种数据结构缝在一起，于是有了本题。

题目描述

给定一棵 (n) 个点的树。每个点 (u) 有一个动态集合 (S_u)，初始为空。

集合 (S_u) 中的每个元素是一个七元组
[ (x,y,w,l,r,k,b) ] 表示一个定义在区间 ([l,r]) 上的函数 [ f(t)=kt+b ]

你需要支持 (m) 个强制在线操作：

1. 1 u x y w l r k b
   向 (S_u) 中插入一个元素。

2. 2 u x y w l r k b
   从 (S_u) 中删除一个元素，保证存在。

3. 3 u v x1 x2 y1 y2 w1 w2 t
   查询树上路径 (u\to v) 上所有点的集合中，满足
   [ x_1\le x\le x_2,\quad y_1\le y\le y_2,\quad w_1\le w\le w_2,\quad l\le t\le r ] 的元素，求 (f(t)) 的最大值。若不存在输出 -1。

4. 4 u v x1 x2 y1 y2 w1 w2 t k
   同样条件下，求 (f(t)) 的第 (k) 大值。若不存在输出 -1。

强制在线：设 lastans 初始为 (0)，除 (n,m) 和操作类型 op 外，所有输入整数都需要异或 lastans 才是真实值。每次输出后，令 lastans 为本次答案。

输入格式

第一行两个整数 (n,m)。

接下来 (n-1) 行，每行两个整数 (u,v)，表示一条树边。

接下来 (m) 行，每行第一个整数为 op：

• 若 op=1 或 op=2：
  u x y w l r k b
• 若 op=3：
  u v x1 x2 y1 y2 w1 w2 t
• 若 op=4：
  u v x1 x2 y1 y2 w1 w2 t k

输出格式

对每个 op=3 或 op=4，输出一行一个整数表示答案。

样例

输入

1 2
1 1 1 1 1 1 1 2 3
3 1 1 1 1 1 1 1 1 3

输出

9

样例解释

节点 (1) 中插入函数 (f(t)=2t+3)，定义域 ([1,1])。
查询路径 (1\to1)，所有范围都只包含该元素，且 (t=3)，所以答案为
[ 2\times 3+3=9 ]

数据范围

对于 (100%) 数据：

• (1\le n,m\le 10^5)
• 所有坐标、权值、函数参数、查询参数的绝对值不超过 (10^9)
• 保证树连通，删除操作合法
• 时间限制：(1\text{s})
• 空间限制：(4\text{TB})
• 强制在线

提示

本题标准解法为：

[ \text{树状数组套树状数组套权值线段树套线段树套平衡树套李超树套树链剖分} ]

具体来说：

• 树链剖分把路径 (u\to v) 拆成 (O(\log n)) 个 DFS 序区间；
• 外层树状数组维护 (x) 维；
• 内层树状数组维护 (y) 维；
• 权值线段树维护 (w) 维；
• 线段树维护函数定义域 ([l,r])；
• 平衡树维护动态插入与删除；
• 李超树维护 (f(t)) 的最值；
• 最内层再套树链剖分，处理李超树节点内部的函数树路径关系。

单次操作复杂度约为
[ O(\log^7 n) ] 空间复杂度约为
[ O(n\log^6 n) ]

出题人不会写标程，因此本题没有数据。
如果你真想写，建议先写暴力，然后放弃。