seuOJ568 - 广义线段树

• 题目类型：传统
• 输入文件：标准输入流
• 输出文件：标准输出流
• 时间限制：4500 ms
• 空间限制：512 MiB
• 题目标签：Div.1, 2025 帆软杯

题目描述

给定一棵有 $2n-1$ 个节点的二叉树，节点的编号为 $1,2,\cdots,2n-1$。

编号为 $p$ 的节点（下称节点 $p$）有两个给定的整数属性值 $L_p,R_p$，满足 $L_p\le R_p$。

该二叉树还满足以下性质：

• 节点 $1$ 是根，$L_1=1$，$R_1=n$。
• 对于任意一个节点 $p$：
  • 若 $L_p=R_p$，则节点 $p$ 没有子节点。
  • 若 $L_p<R_p$，则节点 $p$ 有两个子节点。在这里，我们区分左右子节点。设节点 $p$ 的左子节点是 $u$，右子节点是 $v$，有 $L_u=L_p$ 且 $R_u+1=L_v$ 且 $R_v=R_p$。

我们称这样的树为广义线段树。

对于任意区间 $[l,r]$ 满足 $l,r$ 均为整数且 $1\le l\le r\le n$，考虑以下算法：

给定 $m$ 个区间 $[l_i,r_i]$（$i=1,2,\cdots,m$），对于每个 $i$ 都执行 $\text{visit}(1,l_i,r_i,i)$ 恰好一次。数组 $\textit{cnt}_1$（下标为 $1,2,\cdots,m$）和 $\textit{cnt}_2$（下标为 $1,2,\cdots,2n-1$）的所有元素初始时均为 $0$，求它们最终的值。

输入格式

第一行两个整数 $n,m$（$1\le n,m\le10^6$）。

接下来 $2n-1$ 行中，第 $i$ 行表示节点 $i$ 的情况：

• 每行先是两个整数 $L_i,R_i$（$1\le L_i\le R_i\le n$）。
• 若 $L_i<R_i$，还有两个整数 $u,v$（$2\le u,v\le2n-1$），分别表示节点 $i$ 的左子节点和右子节点。

接下来 $m$ 行中，第 $i$ 行两个整数 $l_i,r_i$（$1\le l_i\le r_i\le n$）。

输出格式

输出两行。

第一行 $m$ 个整数，其中第 $i$ 个数表示 $\textit{cnt}_1[i]$ 最终的值。

第二行 $2n-1$ 个整数，其中第 $i$ 个数表示 $\textit{cnt}_2[i]$ 最终的值。

样例

输入

4 5
1 4 2 3
1 2 4 5
3 4 6 7
1 1
2 2
3 3
4 4
1 4
2 3
1 1
4 4
2 2

输出

1 5 3 3 3
5 3 2 1 2 1 1