P2496 [SDOI2012] 体育课

# 警告：滥用本题评测将被封号

又是一节体育课的时间了，有 $n$ 个同学排成了一排。他们都很讨厌排在第一个位置的同学，于是后面的同学中比第一个高的都会产生一个高兴值，这个高兴值等于他的身高减去第一个同学的身高。当然比第一个同学矮的同学产生兴奋值为 $0$。 现在体育老师来了，他拥有神奇的魔法，现在他能做如下的三件事： 1. 询问某段区间高兴值最大的那个是多少。 2. 把某两个同学交换一下位置。 3. 选取一段区间的人，把第一个人身高加上 $t$，第二个加上 $2t$，第三个加上 $3t$ 以此类推。 但是体育老师不会数数，于是他找到你了，对于每一个询问，他要你帮他求出那个值。

无

无

#### 数据规模与约定 - 对于 $20\%$ 的数据，保证 $1 \le n,m \le 5 \times 10^3$。 - 另有 $10\%$ 的数据，没有第三种操作。 - 另有 $20\%$ 的数据，没有第二种操作。 - 对于 $100\%$ 的数据，$1 \le n,m \le 10^5$，$0 \le t \le 10^4$，$1 \leq a_i \leq 10^8$。