2153. 快速红包变换

【题目描述】

春节，又是一年一度发红包的时节。

这天晚上，小O睡的正香，她梦见在NOI上拿了金牌，过不了多久，保送清华，进入计算机系，打入ACM，赢取金奖，走上人生巅峰，想想还有点小激动。

这时，残暴的笑声吵醒了小O。

“哈哈！愚蠢的人类！这种纸质的红包早就不能镇压本座了！哈哈！”

“看你一脸懵逼，没错，本座就是‘祟’！愚蠢的人类！用红包镇压了本座千百年！如今！QQ微信红包当世，人类寄托在压岁钱里的信念已经冲淡了！这，正是本座重现大地的契机！哈哈！”

“人类，你是本座遇到的第一个人！你来和本座玩个游戏吧！恩，就用这可恶的红包吧！哈哈！”

“本座，在这里放一些红包，然后！对里面的钱数做一些变换，你，要回答本座的问题，明白的了吗！哈哈！”

【输入格式】

第一行，一个数N，表示红包的数量

第二行，N个数，表示红包A[1]，A[2]……A[N]初始的钱数

第三行，一个数M，表示变换和询问的个数和

第4~3+M行，每行包含一条命令令，和命令的具体细节。

命令如下：

Cadd l r a (add 从A[l]到A[r]每个红包钱数加a)

Cchange l r a (change 从A[l]到A[r]每个红包钱数变为a)

Cbmax l r a (be max 从A[l]到A[r]每个红包钱数变为max(A[i],a))

Cbmin l r a (be min 从A[l]到A[r]每个红包钱数变为min(A[i],a))

Qsum l r (sum 求从A[l]到A[r]每个红包钱数和)

Qwmax l r (what is max 从A[l]到A[r]每个红包钱数的最大值)

Qwmin l r (what is min 从A[l]到A[r]每个红包钱数的最小值)

Qnmax l r (number of max 从A[l]到A[r]每个红包钱数的最大值的个数)

Qnmin l r (number of min 从A[l]到A[r]每个红包钱数的最小值的个数)

【输出格式】

针对每个询问，输出结果，每行一个。

【样例输入1】

10
4 8 4 7 2 2 5 2 9 8
10
Qsum 1 6
Qsum 3 4
Cadd 3 4 8
Cadd 5 6 6
Qsum 6 9
Cadd 7 8 4
Qsum 8 8
Cadd 7 8 8
Cadd 2 5 2
Cadd 7 10 1

【样例输出1】

27
11
24
6

【样例输入2】

10
7 4 4 0 8 1 1 9 3 3
10
Cbmin 2 10 3
Qsum 2 7
Cbmax 2 8 5
Cbmin 2 4 5
Qsum 9 10
Cadd 3 6 9
Cbmin 10 10 7
Qnmax 7 7
Qnmax 4 5
Cadd 4 9 2

【样例输出2】

11
6
1
2

【提示】

各组数据N，M取值，指令种类如下

10 10 Cadd Qsum

1000 1000 Cadd Cchange Qsum

100000 100000 Cadd Cchange Qsum

100000 100000 Cadd Cchange Qsum

100 100 全部

10000 10000 全部

10000 10000 全部

100000 100000 全部

100000 100000 全部

100000 100000 全部

题目中全部数据可用int保存

【来源】

UBWH

UPD：2017.9.15新添数据一组By Mike，现在复杂度不对的算法都跪了……