数据结构

题目背景

**引言** 数据结构学的好,未来工作没烦恼。 ![](https://timgsa.baidu.com/timg?image&quality=80&size=b9999\_10000&sec=1508946101936&di=0c08b703e466d2a3b2d20dd8008821fc&imgtype=0&src=http%3A%2F%2Fjoymepic.joyme.com%2Farticle%2Fuploads%2Fallimg%2F201511%2F1446516425349678.gif) Edgration 是一个喜欢乱搞数据结构的蒟蒻(以下简称edt),有一天,他作死想去刁难一下dalao: edt想求一种数据结构,使得可以实现区间加,求出某一区间大于k的元素的个数 dalao1:sb线段树 dalao2:sb分块 dalao3:sb平衡树 edt: 不行,那就加上取模,求区间取膜mod后大于MIN小于MAX的元素个数 dalao1:线段树&……¥#&……%……&\*&%¥ dalao2:sb分块 &%¥……%#¥#&……&\* dalao3:\*&……%&¥LCT维护SBT水题 &……%&……% edt:那不仅取模,每个数乘上数组下标再取模 dalao:¥%¥¥&\*(#¥% 叽里呱啦叽里呱啦 edt:不行,在把取模的值丢到一棵树上,维护一棵仙人掌乘积方差的最小极差 dalao:替罪羊树上用sb块状链表维护Toptree上的最小费用最大流和可持久化仙人掌,算出来在基尔霍夫矩阵中反演后跑一遍fft维护的插头DP就好了,给我三分钟轻松水过。。 edt:mmp

题目描述

蒟蒻Edt把这个问题交给了你 ———— 一个精通数据结构的大犇,由于是第一题,这个题没那么难。。 edt 现在对于题目进行了如下的简化: 最开始的数组每个元素都是0 给出$n$,$opt$,$mod$,$min$,$max$,$mod$在int范围内 操作$A$,$Q$ $A$: $L$,$R$,$X$ 表示把$[l,R]$这个区间加上$X$ **(数组的从L到R的每个元素都加上X)** $Q$: $L$,$R$ 表示询问$[L,R]$这个区间中元素T满足 $min<=(T*i$%$ mod)<=max$ 的 T这样的数的个数(i是数组下标) **(元素的值\*数组下标%mod在min到max范围内)** 由于 edt 请来了一位非三次元的仓鼠,他帮你用延后了部分问题,将这些询问打入了混乱时空,你的询问操作不会超过1000次,不幸的是,对于延后的询问操作可能有很多次(小于1e7次),但是保证这些延后的询问操作之后不会再次有修改操作 (就是在最后会有很多次询问,但不会进行修改)

输入输出格式

输入格式


给出n,opt,mod,min,max表示序列大小,操作次数,取膜,最小值,最大值 下面opt行,给出 $A$: $L$,$R$,$X$表示区间加,保证X在int范围内(<2147483647) $Q$:$L$,$R$表示区间查询满足条件的个数 再给出一个$Final$值,表示后面有$Final$个询问 下面$Final$行,给出 $L$,$R$表示询问区间$[L,R]$表示询问$[L,R]$之间满足条件的个数

输出格式


每行对于每个$Q$操作输出$Q$个数表示每次询问的值, 下面$Final$行表示$Final$个询问的值

输入输出样例

输入样例 #1

3 2 4 0 2
A 1 3 5
Q 2 3 
5
1 3
2 3
1 1 
2 2 
3 3

输出样例 #1

1
2
1
1
1
0

输入样例 #2

17 25 4098 310 2622
A 10 16 657212040
A 4 15 229489140
A 1 2 -433239891
A 3 12 532385784
A 10 17 56266644
A 8 10 10038874
A 6 9 13084764
A 4 5 -9206340
Q 2 8
A 2 4 -43223955
A 6 9 31478706
A 2 4 189818310
A 2 8 179421180
A 2 8 40354938
Q 8 14
A 3 6 57229575
A 6 13 132795740
A 2 17 14558022
A 14 15 -552674185
A 5 11 -1104138
Q 2 12
Q 1 14
A 3 9 524902182
A 8 12 114291440
A 3 7 107531442
1
11 12

输出样例 #2

3
6
7
8
2

输入样例 #3

20 3 4317 1020 2232
A 8 15 -434078222
A 1 2 54988154
A 13 19 81757858
15
7 11
3 5
3 9
6 9
9 13
6 19
1 20
3 5
3 10
1 7
2 14
6 10
2 3
2 3
10 12

输出样例 #3

0
0
0
0
0
2
2
0
0
0
0
0
0
0
0

说明

## 样例说明 给出样例1的解释: 样例1中,$a$数组修改为$5$,$5$,$5$ 每个$a[i]*i$%$4$ 的值为$1$,$2$,$3$ 对于Final的询问 询问$[1$,$3]$中大于等于0小于等于2的个数为2个 剩下的询问类似 ## 题目说明 **注意**: ### 1.关于负数取模问题,请以 c++ 的向0取整为标准,即如: [ $ -7 $%$ 3 = -1 $ ] [ $ 7 $%$ 3 = 1 $ ] ### 2.一共会有50个测试点,每个点分值为2分。 因为测试点数较多,请oier们自觉地不要故意多次提交来卡评测机,出题人 edt 在这里表示由衷的感谢 ## 数据范围 如果你不能作对所有点,请尝试获得部分分,所有数据都是随机生成 ![img](http://ww4.sinaimg.cn/large/0060lm7Tly1fkvxd8ty5bj30ld09labf.jpg)