P3373 【模板】线段树 2
- 47通过
- 186提交
- 题目提供者HansBug
- 标签
- 难度提高+/省选-
提交 讨论 题解
最新讨论
- 为啥WA(TAT)
题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数加上x
2.将某区间每一个数乘上x
3.求出某区间每一个数的和
输入输出格式
输入格式:
第一行包含三个整数N、M、P,分别表示该数列数字的个数、操作的总个数和模数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x y k 含义:将区间[x,y]内每个数乘上k
操作2: 格式:2 x y k 含义:将区间[x,y]内每个数加上k
操作3: 格式:3 x y 含义:输出区间[x,y]内每个数的和对P取模所得的结果
输出格式:
输出包含若干行整数,即为所有操作3的结果。
输入输出样例
输入样例#1:
5 5 38
1 5 4 2 3
2 1 4 1
3 2 5
1 2 4 2
2 3 5 5
3 1 4
输出样例#1:
17
2
说明
时空限制:1000ms,128M
数据规模:
对于30%的数据:N<=8,M<=10
对于70%的数据:N<=1000,M<=10000
对于100%的数据:N<=100000,M<=100000
(数据已经过加强^_^)
样例说明:
故输出应为17、2(40 mod 38=2)
分析:参见:传送门,一模一样.
洛谷P3373 【模板】线段树 2的更多相关文章
-
洛谷P3373 [模板]线段树 2(区间增减.乘 区间求和)
To 洛谷.3373 [模板]线段树2 题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.将某区间每一个数乘上x 3.求出某区间每一个数的和 输入输出格式 输入格 ...
-
线段树_区间加乘(洛谷P3373模板)
题目描述 如题,已知一个数列,你需要进行下面三种操作: 1.将某区间每一个数乘上x 2.将某区间每一个数加上x 3.求出某区间每一个数的和 输入格式: 第一行包含三个整数N.M.P,分别表示该数列数字 ...
-
洛谷 - P1198 - 最大数 - 线段树
https://www.luogu.org/problemnew/show/P1198 要问区间最大值,肯定是要用线段树的,不能用树状数组.(因为没有逆元?但是题目求的是最后一段,可以改成类似前缀和啊 ...
-
洛谷 P2391 白雪皑皑 线段树+优化
题目描述: 现在有 \(N\) 片雪花排成一列. Pty 要对雪花进行$ M $次染色操作,第 \(i\)次染色操作中,把\((i*p+q)%N+1\) 片雪花和第\((i*q+p)%N+1\)片雪花 ...
-
【洛谷】【线段树】P1471 方差
[题目背景:] 滚粗了的HansBug在收拾旧数学书,然而他发现了什么奇妙的东西. [题目描述:] 蒟蒻HansBug在一本数学书里面发现了一个神奇的数列,包含N个实数.他想算算这个数列的平均数和方差 ...
-
【洛谷】【线段树】P1047 校门外的树
[题目描述:] 某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米.我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置:数轴上的每个整数点,即0,1,2,……,L ...
-
【洛谷】【线段树】P1886 滑动窗口
[题目描述:] 现在有一堆数字共N个数字(N<=10^6),以及一个大小为k的窗口.现在这个从左边开始向右滑动,每次滑动一个单位,求出每次滑动后窗口中的最大值和最小值. [输入格式:] 输入一共 ...
-
【洛谷】【线段树】P3353 在你窗外闪耀的星星
[题目描述:] /* 飞逝的的时光不会模糊我对你的记忆.难以相信从我第一次见到你以来已经过去了3年.我仍然还生动地记得,3年前,在美丽的集美中学,从我看到你微笑着走出教室,你将头向后仰,柔和的晚霞照耀 ...
-
洛谷P5280 [ZJOI2019]线段树
https://www.luogu.org/problemnew/show/P5280 省选的时候后一半时间开这题,想了接近两个小时的各种假做法,之后想的做法已经接近正解了,但是有一些细节问题理不 ...
-
洛谷P3374(线段树)(询问区间和,支持单点修改)
洛谷P3374 //询问区间和,支持单点修改 #include <cstdio> using namespace std; ; struct treetype { int l,r,sum; ...
随机推荐
-
SQL Server 2012故障转移的looksalive check和is alive check
什么是looksalive check和is alive check SQL Server故障转移集群是建立在windows集群服务上的一种热备的高可用方案.在集群运行过程中,windows集群服务定 ...
-
【C#】依赖于SharpZipLib的Zip压缩工具类
上班第二天下班,课外作业,实现一个ZIP压缩的工具类.本来想用Package,但是写完了才发现不能解压其他工具压缩的zip包,比较麻烦,因此本工具类依赖了第三方的库(SharpZipLib vers ...
-
ACM题目————Aggressive cows
Description Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stal ...
-
一款jquery写出来的tab切换
当时做这个的时候,当前状态是不规则的,li对应的有3块内容,分别设定不同背景图片,只显示当前的一个背景,鼠标移上去的时候其余2个用background-position: -1000px 0px;来隐 ...
-
math。h中的log函数的应用
以10为底的log函数: 形式为 double log10(double x) 以e为底的log函数(即 ln)double log (double x) 如何表达log 以a为底b的对数: 用换 ...
-
jps查看java进程中哪个线程在消耗系统资源
jps或ps -ef|grep java可以看到有哪些java进程,这个不用说了.但值得一提的是jps命令是依赖于/tmp下的某些文件 的. 而某些操作系统,定期会清理掉/tmp下的文件,导致jps无 ...
-
Date与SimpleDateFormat
Date常用的方法 返回类型 方法名称 备注 Date New Date() 创建当前日期对象 Date New date(long dt) 使用自1970.1.1以后的指定毫秒数创建日期 boole ...
-
vue 动态循环出的多个select 不能重复选择相同的数据
看图说话 HTML: JS: 1) 2) 3) 有更好的方法可以相互学习.
-
linux C sscanf()函数
linux sscanf() 类似正则表达式,又不完全是正则表达式. 分割 ”/“ 或 "@" 或空格 要用 [^/] 例如: sscanf("iios/12DDWDFF ...
-
(转)SDL 1.2 to 2.0 Migration Guide--SDL1.2更新到SDL2.0指南
SDL 1.2 to 2.0 Migration Guide 目录 SDL 1.2 to 2.0 Migration Guide Translations Introduction Overview ...