当前位置:首页 > 数据结构 > 线段树 > 正文
洛谷P3373【模板】线段树2
2896+

题目大意:对一个数列,实现区间加x、区间乘x以及区间求和操作。

题目描述

如题,已知一个数列,你需要进行下面两种操作:

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

(数据已经过加强^_^)

解题思路

线段树的线段记录区间的和,需要区间加和区间乘,那就打两个标记,a记录儿子还没加的数,t记录儿子还没乘的数。多个标记,加和乘谁先算呢?我们规定,先算乘的标记,再算加的标记。那么,打标记的时候,如果是加号,就直接累加到加标记,与成标记无关;如果乘号,那么乘标记累乘,加标记也跟这累乘一下。如一条线段加标记a=5、乘标记t=2,标记下放前儿子的值是d,那么儿子的现在实际的值应该是d*t+a,再次基础上再乘上乘标记,即(d*t+a)*乘标记,显然原来的加标记和乘标记都要乘一下!线段的值如何更新?如果是加,就区间每个元素都加,加上增量即可;如果是乘,区间每个数乘,也就是和乘标记,d直接成标记即可。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,

洛谷P3373【模板】线段树2:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!