P6272 [湖北省队互测2014] 没有人的算术

题目来源：$2014$ 年湖北省队互测Week1 资源来源：[链接](https://tieba.baidu.com/p/3050650090?red_tag=3002680446)

万物初始之前，宇宙是无边无际混沌的黑暗，只有上帝之灵穿行其间。 上帝对这无边的黑暗十分不满，就一挥手说:“要有光”，于是世间就有了光。从此，世间 就有了昼与夜的交替。这是上帝创世的第一天。 第二天，上帝仍不满意眼前空洞的景象，就一挥手说：“要有零”。于是世间出现了第一个数：$0$。 第三天，上帝对只有 $0$ 很不满意，就一挥手说：“要有非零数”。于是上帝开始创造新数，每个新数用一个已经创造出来的数的有序对表示，即： $$ x = (x_L, x_R) $$ 于是世间出现了 $(0, 0), (0, (0, 0)), ((0, 0), 0), ((0, 0), (0, 0)), ...$。到了晚上，各种各样千奇百怪的数在大地上奔腾。 （注：上帝造的这个 “数” 与普通的自然数、有理数之类的不同，这种数是以如上所述的方式递归定义的，总是数对里面是数对，拆分到最后会得到不可再拆的 $0$） 第四天，上帝看到各个数不分彼此，就一挥手说：“要有区别”。于是为了区分每个数，上帝定义等于： 1. $0 = 0$ 。 2. 对于任意 $x_L, x_R, y_L, y_R$，若 $x_L = y_L$ 且 $x_R = y_R$，则 $(x_L, x_R) = (y_L, y_R)$。 3. 对于任意 $x, y$，$x = y$ 当且仅当满足以上条件之一。反之记作 $x \not = y$。 第五天，上帝看到各个数乱成一团，就一挥手说：“要有序”。于是为了比较每个数，上帝定义小于： 1. 对于任意 $x$，若 $x\not = 0$，则 $0 < x$。 2. 对于任意 $x_L, x_R, y_L, y_R$，若 $x_L < y_L$，则 $(x_L, x_R) < (y_L, y_R)$ 。 3. 对于任意 $x_L, x_R, y_L, y_R$，若 $x_L = y_L$ 且 $x_R < y_R$，则 $(x_L, x_R) < (y_L, y_R)$。 4. 对于任意 $x, y$，$x < y$ 当且仅当满足以上条件之一。反之记作 $x\not < y$。 在此基础上定义小于等于：$x ≤ y \iff x < y$ 或 $x = y$ 。容易发现： 1. $x ≤ y, y ≤ x ⇒ x = y$ 。 2. $x ≤ y, y ≤ z ⇒ x ≤ z$ 。 3. $x ≤ y$ 或 $y ≤ x$ 。 进而定义： 1. $x > y \Longleftrightarrow y < x$ 。 2. $x ≥ y \Longleftrightarrow x\not < y$。 至此万物欣欣向荣，和睦一堂。 第六天，由于之前沉迷与算术而忘记去造核酸和蛋白质，所以上帝没办法造人。但是上帝不甘心，就一挥手说：“要有跳蚤”，于是用泥巴捏出了神奇生物跳蚤。 上帝用五天的时间造出天地万物，又在第六天造出了唯一的生命——跳蚤。上帝看到天地万物井然有序、生生不息，自己造的跳蚤正在开心地和数学玩耍，很高兴，便决定把第七天作为休息的日子。 跳蚤每天的生活很简单。一天开始时，他会取一个长度为 $n$ 的数组 $a[1,2,\cdots,n]$，初始时均为 $0$。 接着他会不断地做下列两件事之一： 1. 在头脑中产生三个正整数 $l, r, k$，然后把 $a[k]$ 重新赋值为 $(a[l], a[r])$ 。特别地，如果 $l = k$ 或 $r = k$ 也是合法的，这不会导致错误，因为跳蚤总是先默默算出 $(a[l], a[r])$ 再给 $a[k]$ 赋值。 保证 $1 ≤ l, r, k ≤ n$。 2. 在头脑中产生两个正整数 $l, r$，然后计算 $a[l], a[l + 1], \cdots, a[r − 1], a[r]$ 中的最大值。 保证 $1 ≤ l ≤ r ≤ n$。 跳蚤当然知道怎么做啦！但是他想考考你……

无

无

$$ \def\arraystretch{1.5} \begin{array}{c|l|l} \hline\hline \rm Task~Id & n & m \\ \hline\hline 1 & =10 & =50 \\ \hline 2 & =5\times 10^4 & \leq 2\times 10^5 \\ \hline 3 & =5\times 10^4 & \leq 2\times 10^5 \\ \hline 4 & =6\times 10^4 & \leq 5\times 10^5 \\ \hline 5 & =6\times 10^4 & \leq 5\times 10^5 \\ \hline 6 & =8\times 10^4 & \leq 2\times 10^5 \\ \hline 7 & =8\times 10^4 & \leq 2\times 10^5 \\ \hline 8 & =10^5 & \leq 5\times 10^5 \\ \hline 9 & =10^5 & \leq 5\times 10^5 \\ \hline 10 & =10^5 & \leq 5\times 10^5 \\ \hline\hline \end{array} $$