2961. [SYOI 2018] 简单的线段树

【题目描述】

线段树的结构非常简单，它简单到只支持两类操作，修改和查询。

HA实验有一棵线段树，调皮的HtBest想对它进行一些操作，并实时查看他的状态。HtBest会对线段树进行以下三种操作：

1.让线段树维护的区间中[l,r]全部加上一个正整数 

2.让线段树维护的区间中[l,r]全部乘以一个正整数 

3.HtBest希望知道区间[l,r]的数值之和

由于答案可能很大，你只需要输出答案模p后的值。(线段树初始值全为0)

【输入格式】

第一行包含三个正整数n(维护的最大区间)m(操作个数)和p(需要模的值)。接下来有m行，每行描述一个操作，有以下三种形式：

“1 l r v” 表示为[l,r]中的每个数都加上v，

“2 l r v”表示为[l,r]中的每个数都乘以v，

“3 l r”表示查询[l,r]的数值之和。

【输出格式】

对于每个询问操作，输出一个整数占一行，表示询问的答案。

【样例输入1】

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

【样例输出1】

1

【样例输入2】

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

【样例输出2】

0

【样例输入3】

7 7 1000
1 3 5 8
1 2 4 13
2 6 7 2
2 2 4 1
3 1 4
3 4 6
2 1 4 6

【样例输出3】

55
29

【提示】

对于前30%的数据，1≤n，m≤1000

另有20%的数据，无操作2

对于前100%的数据，1≤n，m≤100000

对于所有输入数据，不超过100000000。

暴力程序请加大数据剪枝，否则会卡评测机。

【来源】