Logo Universal Online Judge

UOJ

时间限制:8 s 空间限制:64 MB

#871. ALADIN

Statistics

给定一个N和Q,表示有N个篮子(编号从1到N)和Q个操作,$1 \le N \le 1 000 000 000$) ($1 \le Q \le 50000$,接下来Q行,每行表示一个操作,操作共有两类,第一类以1开头后面跟4个数,如:"1 L R A B" ($1 \le L \le R \le N$) ($1\le A, B \le 1 000 000$), 表示要按规则把蓝子中的石头设成一定的数(规则后面说明);第二类以数字2开头后面跟两个数如:"2 L R",($1 \le L \le R \le N$).表示询问L和R间(包括端点)的所有篮子中的石头个数。
规则:
"1 L R A B",表示重新设置编号从L到R的篮子内的石头(编号为X的篮子设成$(x-L+1)\times A \ mod \ B$.
SCORING
Test cases worth 30% total points have $N \ and\ Q \le 1000$.
Test cases worth 70% total points have $Q \le 1000$.

SAMPLE TESTS

input
6 3
2 1 6
1 1 5 1 2
2 1 6
output
0
3

input
4 5
1 1 4 3 4
2 1 1
2 2 2
2 3 3
2 4 4
output
3
21
0

input
4 4
1 1 4 7 9
2 1 4
1 1 4 1 1
2 1 4
output
16
0
第一个样例说明 最开始篮子为空{0, 0, 0, 0, 0, 0}, 0 stones . 执行第二步: {1 mod 2, 2 mod 2, 3 mod 2, 4 mod 2,5 mod 2, 0} = {1,0,1,0,1,0}, 3 stones in total.