题目名称 2961. HtBest的简单线段树
输入输出 easilysegmenttree.in/out
难度等级 ★★☆
时间限制 1000 ms (1 s)
内存限制 256 MB
测试数据 100 简单对比
题目来源 2018-07-20
开放分组 全部用户
提交状态
分类标签
线段树 HtBest
通过:6, 提交:36, 通过率:16.67%
Gravatarsdzwyq 100 14.577 s C++
GravatarHtBest 100 15.147 s C++
Gravatarjekyll 100 20.473 s C++
GravatarThatXX 100 21.712 s C++
GravatarThatXX 100 21.833 s C++
GravatarThatXX 100 22.225 s C++
Gravatarjekyll 100 22.658 s C++
Gravatarjekyll 100 22.910 s C++
Gravataryouming1 100 23.710 s C++
Gravataryouming1 100 23.780 s C++
关于 HtBest的简单线段树 的讨论
和“行星序列重题”
Gravatar_Itachi
2018-07-20 20:22 1楼
膜膜膜HtBest神犇
被这道简单的线段树卡的死去活来
GravatarNameNotFoundExce
2018-08-09 17:21 2楼

2961. HtBest的简单线段树

★★☆   输入文件:easilysegmenttree.in   输出文件:easilysegmenttree.out   简单对比
时间限制:1 s   内存限制:256 MB

【题目描述】


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

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

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

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

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

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


【输入格式】


第一行包含三个正整数n(维护的最大区间)m(操作个数)和p(需要模的值)。接下来有n行,每行描述一个操作,有以下三种形式:“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。

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

【来源】

By : HtBest