#P1938. [CROATIAN2010] ALADIN

    ID: 960 传统题 1000ms 64MiB 尝试: 142 已通过: 31 难度: 8 上传者: 标签>CF2400提高+/省选-类欧几里得算法懒标记线段树离散化欧几里得算法等差数列求和周期规律验证

[CROATIAN2010] ALADIN

[COCI2009-2010#1] ALADIN

题目描述

有 nn 个盒子,编号为 11 到 nn,每个盒子里最初有 00 颗石头。接下来依次执行 qq 个操作,操作有两种:

  • 第一种操作输入格式为 1 L R A B,表示将编号为 LL 到 RR 的盒子里的石头数量变为 (X−L+1)×A mod B(X-L+1) \times A \bmod B,其中 XX 为盒子的编号。
  • 第二种操作输入格式为 2 L R,表示查询编号为 LL 到 RR 的盒子里的石头总数。

输入格式

第一行有两个数字 nn(1≤n≤1091 \leq n \leq 10^9),qq (1≤q≤5×1041 \leq q \leq 5 \times 10^4)。

接下来 qq 行,每行一个操作。两种操作都满足 1≤L≤R≤n1\le L\le R\le n。第一种操作还满足 1≤A,B≤1061\le A,B\le10^6。

输出格式

对于每个第二种操作,输出石头总数。

样例 #1

样例输入 #1

6 3
2 1 6
1 1 5 1 2
2 1 6

样例输出 #1

0
3

样例 #2

样例输入 #2

4 5
1 1 4 3 4
2 1 1
2 2 2
2 3 3
2 4 4

样例输出 #2

3
2
1
0

样例 #3

样例输入 #3

4 4
1 1 4 7 9
2 1 4
1 1 4 1 1
2 1 4

样例输出 #3

16
0

提示

  • 对于 30%30\% 的数据,n,q≤103n, q \leq 10^3;
  • 对于 70%70\% 的数据,q≤103q \leq 10^3。

题目来源