U407327 Otue 的14个问题

预定时限：$\rm 5s$，预定空间 $\rm 1024MB$。

给定长度为 $n$ 的序列 $a$，进行以下 $m$ 次操作。 * 操作 $1$：$l,r,x$：给 $[l,r]$ 加上一个数 $x$。 * 操作 $2$：$l,r,x$：将 $[l,r]$ 赋值为同一个数 $x$。 * 操作 $3$：$l,r,x$：求出 $[l,r]$ 的和。 * 操作 $4$：询问区间 $[l,r]$ 选出至多 $k$ 个不相交的字段和的最大值。 * 操作 $5$：$l,r,k$：求出 $[l,r]$ 中第 $k$ 小数。 * 操作 $6$：$l,x$：在第 $l$ 个数的前面插入一个数 $x$。 * 操作 $7$：$l,r,x$：询问 $[l,r]$ 区间中是否存在两个下标不同的数的差值为 $x$。 * 操作 $8$：$l,r,x$：询问 $[l,r]$ 区间中是否存在两个下标不同的数的和为 $x$。 * 操作 $9$：$l,r$：询问 $[l,r]$ 的不同数的数量。 * 操作 $10$：$l,r$：询问 $[l,r]$ 的 mex. * 操作 $11$：$l,r,k$：询问 $[l,r]$ 中 $k$ 出现了多少次。 * 操作 $12$：$l,r$：询问 $[l,r]$ 的众数。 * 操作 $13$：$l,r,x,y$：将 $[l,r]$ 区间内所有是 $x$ 的数改为 $y$。 * 操作 $14$：取消第 $i$ 次操作。保证此操作未取消且不是询问。

输入 $n,m$，序列长度，操作次数。 略。

无

对于 $3\%$ 的数据，保证 $1\leq n,m\leq 10^2$，操作 $4$ 的 $k$ 为 $1$。 对于 $10\%$ 的数据，保证 $1\leq n,m\leq 10^2$。 对于 $20\%$ 的数据，保证 $1\leq n,m\leq 7\times10^3$。 对于另外 $20\%$ 的数据，保证 $1\leq a_i\leq5$。 对于另外 $20\%$ 的数据，保证数据随机生成。 对于 $100\%$ 的数据，保证 $1\leq n\leq 5\times 10^4,1\leq m\leq 3\times 10^5$。 保证任意时刻序列中的数 $a_i$ 满足 $-10^4\leq a_i\leq 10^4$，操作 $4$ 中 $k\leq 10$，操作 $6$ 出现次数不会大于 $\sqrt m$。