P3372 【模板】线段树 1
- 153通过
- 525提交
- 题目提供者HansBug
- 标签
- 难度普及+/提高
提交 讨论 题解
最新讨论
- 【模板】线段树1(AAAAAAAAA…
- 【模板】线段树1
- 洛谷评测机出问题了吗?
题目描述
如题,已知一个数列,你需要进行下面两种操作:
1.将某区间每一个数加上x
2.求出某区间每一个数的和
输入输出格式
输入格式:
第一行包含两个整数N、M,分别表示该数列数字的个数和操作的总个数。
第二行包含N个用空格分隔的整数,其中第i个数字表示数列第i项的初始值。
接下来M行每行包含3或4个整数,表示一个操作,具体如下:
操作1: 格式:1 x y k 含义:将区间[x,y]内每个数加上k
操作2: 格式:2 x y 含义:输出区间[x,y]内每个数的和
输出格式:
输出包含若干行整数,即为所有操作2的结果。
输入输出样例
输入样例#1:
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
输出样例#1:
11
8
20
说明
时空限制:1000ms,128M
数据规模:
对于30%的数据:N<=8,M<=10
对于70%的数据:N<=1000,M<=10000
对于100%的数据:N<=100000,M<=100000
(数据已经过加强^_^,保证在int64/long long数据范围内)
分析:涉及到区间操作,那么利用lazy-tag思想,当需要处理到本区间时,不必往下处理,打上标记,当需要用的时候下传标记即可.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; long long n, m,sum[],tag[]; void pushdown(int l, int r, int o)
{
if (tag[o])
{
int mid = (l + r) >> ;
tag[o * ] += tag[o];
tag[o * + ] += tag[o];
sum[o * ] += tag[o] * (mid - l + );
sum[o * + ] += tag[o] * (r - mid);
tag[o] = ;
}
} void build(int l, int r, int o)
{
if (l == r)
{
scanf("%lld", &sum[o]);
return;
}
int mid = (l + r) >> ;
build(l, mid, o * );
build(mid + , r, o * + );
sum[o] = sum[o * ] + sum[o * + ];
} void update(int L, int R, int v, int l, int r, int o)
{
if (L <= l && r <= R)
{
tag[o] += v;
sum[o] += v * (r - l + );
return;
}
pushdown(l, r, o);
int mid = (l + r) >> ;
if (L <= mid)
update(L, R, v, l, mid, o * );
if (R > mid)
update(L, R, v, mid + , r, o * + );
sum[o] = sum[o * ] + sum[o * + ];
} long long query(int L, int R, int l, int r, int o)
{
if (L <= l && r <= R)
return sum[o];
if (L > r || R < l)
return ;
pushdown(l, r, o);
int mid = (l + r) >> ;
return query(L, R, l, mid, o * ) + query(L, R, mid + , r, o * + );
} int main()
{
scanf("%lld%lld", &n, &m);
build(, n, ); for (int i = ; i <= m; i++)
{
int id, x, y, k;
scanf("%d", &id);
if (id == )
{
scanf("%d%d%d", &x, &y, &k);
update(x, y, k, , n, );
}
if (id == )
{
scanf("%d%d", &x, &y);
printf("%lld\n", query(x,y,,n,));
}
} return ;
}
洛谷P3372 【模板】线段树 1的更多相关文章
-
洛谷P3373 [模板]线段树 2(区间增减.乘 区间求和)
To 洛谷.3373 [模板]线段树2 题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.将某区间每一个数乘上x 3.求出某区间每一个数的和 输入输出格式 输入格 ...
-
洛谷 - 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; ...
-
洛谷 P5280 - [ZJOI2019]线段树(线段树+dp,神仙题)
题面传送门 神仙 ZJOI,不会做啊不会做/kk Sooke:"这八成是考场上最可做的题",由此可见 ZJOI 之毒瘤. 首先有一个非常显然的转化,就是题目中的"将线段树 ...
随机推荐
-
C#图片按比例缩放
C#图片按比例缩放: // 按比例缩放图片 public Image ZoomPicture(Image SourceImage, int TargetWidth, int TargetHeight) ...
-
页面引入flash
function shFlashObj(id, data, oWidth, oHeight, flashvals,beFullScreen) { var swf='<object id=& ...
-
转:对于服务器AdminServer, 与计算机Machine-0相关联的节点管理器无法访问
控制台启动server时报"对于服务器server-1与计算机machin<!--StartFragment -->对于服务器AdminServer, 与计算机Machine-0 ...
-
nginx负载均衡 - session失效
最近迷上了Nginx,真实麻雀虽小,五脏俱全..功能实在强大.. nginx不单可以作为强大的web服务器,也可以作为一个反向代理服务器,而且nginx还可以按照调度规则实现动态.静态页面的分离,可以 ...
-
主线程中有多个handler的情况
工作中遇到了这么一种情况,有两个视图,都需要开启异步任务从服务器获取数据,每个view中创建一个Handler,注册到异步任务中去,当异步任务从服务器获取数据出错,或者出现io异常或者http协议异常 ...
-
Oracle由ID生成父ID的函数
/*表结构*/ CREATE TABLE ly_md ( bh BYTE), mc BYTE), pym BYTE), f_bh BYTE), ch NUMBER, ID NUMBER ); INSE ...
-
css修改滚动条默认样式
之前因为公司项目需要,在网上找到的: 直接上代码了 html代码 <div class="inner"> <div class="innerbox&qu ...
-
keepalived结合nginx实现nginx高可用
1.简介 Keepalived 是一个基于VRRP协议来实现的LVS服务高可用方案,可以利用其来避免单点故障.一个LVS服务会有2台服务器运行Keepalived,一台为主服务器(MASTER),一台 ...
-
DDGScreenShot—图片擦除功能
写在前面 图片擦除功能,也是运用图片的绘制功能, 将图片绘制后,拿到相应的图片.当然,有一涨底图更明显 实现代码如下 /** ** 用手势擦除图片 - imageView --传图片 - bgView ...
-
为什么python中没有switch case语句
终于知道了python中映射的设计哲学. 我自己写的code : class order_status_switcher(object): def get_order_status(self,argu ...