[Ynoi2007] rgxsxrs

题目背景

本题读入量约 15 MB,输出量约 13 MB,请选择合适的输入输出方法。

题目描述

给定一个长为 $n$ 的序列 $a$,需要实现 $m$ 次操作: `1 l r x`:表示将区间 $[l,r]$ 中所有 $>x$ 的元素减去 $x$。 `2 l r`:表示询问区间 $[l,r]$ 的和,最小值,最大值。

输入输出格式

输入格式


第一行两个正整数 $n,m$。 第二行 $n$ 个正整数表示序列 $a$。 之后 $m$ 行每行 $3$ 或 $4$ 个正整数表示一次操作。 **本题强制在线,所有输入的 $l,r,x$ 均需要异或 $lastans$,其定义为上一次询问操作得到的区间和对 $2^{20}$ 取模后的值,若之前没有询问操作,则为 $0$。**

输出格式


对于每个操作 $2$ ,输出一行三个用空格分隔的数表示答案。

输入输出样例

输入样例 #1

5 5
2 4 5 1 3
1 2 4 3
2 1 5
2 10 12
1 7 3 7
2 5 3

输出样例 #1

9 1 3
6 1 3
4 1 2

说明

Idea:wangziji&花花,Solution:wangziji&花花,Code:ccz181078,Data:wangziji&花花&ccz181078 注意:本题采用**捆绑测试**,只有当你通过一个 subtask 中的所有测试点后,你才能拿到这个 subtask 的分数。 对于 $1\%$ 的数据,$n,m\leq 1000$,时限为 3s。 对于另外 $14\%$ 的数据,$a_i\leq 10$,$n,m\leq 2\times10^5$,时限为 3s。 对于另外 $19\%$ 的数据,$a_i\leq 1000$,$n,m\leq 2\times10^5$,时限为 3s。 对于另外 $19\%$ 的数据,$a_i\leq 2\times 10^5$,$n,m\leq 2\times10^5$,时限为 3s。 对于 $100\%$ 的数据,$1\le n,m\leq 5\times 10^5$,$1\leq a_i,x\leq 10^9$。