洛谷—— P3372 【模板】线段树 1
2024-09-25 01:32:27
P3372 【模板】线段树 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数据范围内)
样例说明:
线段树模板
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define N 4000001 using namespace std; long long ans; int n,m,q,x,y,a,b; int read() { ,f=; char ch=getchar(); ; ch=getchar();} +ch-'; ch=getchar();} return x*f; } struct Tree { int l,r,f;long long w; }tree[N]; void build(int k,int l,int r)//建树 { tree[k].l=l,tree[k].r=r; if(tree[k].l==tree[k].r) { tree[k].w=read(); return ; } ; build(k<<,l,m); build(k<<|,m+,r); tree[k].w=tree[k<<].w+tree[k<<|].w; } void down(int k)//标记下传 { tree[k<<].f+=tree[k].f; tree[k<<|].f+=tree[k].f; tree[k<<].w+=tree[k].f*(tree[k<<].r-tree[k<<].l+); tree[k<<|].w+=tree[k].f*(tree[k<<|].r-tree[k<<|].l+); tree[k].f=; } void change_point(int k)//单点修改 { if(tree[k].l==tree[k].r) { tree[k].w+=y; return ; } if(tree[k].f) down(k); ; ); |); tree[k].w=tree[k<<].w+tree[k<<|].w; } void ask_point(int k)//单点查询 { if(tree[k].l==tree[k].r) { ans=tree[k].w; return ; } if(tree[k].f) down(k); ; ); |); } void change_interval(int k)//区间修改 { if(tree[k].l>=a&&tree[k].r<=b) { tree[k].w+=y*(tree[k].r-tree[k].l+); tree[k].f+=y; return ; } if(tree[k].f) down(k); ; ); |); tree[k].w=tree[k<<].w+tree[k<<|].w; } void ask_interval(int k)//区间查询 { if(tree[k].l>=a&&tree[k].r<=b) { ans+=tree[k].w; return ; } if(tree[k].f) down(k); ; ); |); } int main() { n=read();m=read(); build(,,n); while(m--) { q=read();ans=; ) { a=read(),b=read(),y=read(); change_interval(); } else { a=read(),b=read(); ask_interval(); printf("%lld\n",ans); } } ; }
最新文章
- Abp集成Swagger的最佳实践
- 什么是“鸭子类型(duck typing)”?
- 输出string vector到file
- HDU 4617 Weapon 三维计算几何
- RHEL 7 命令行注册和激活订阅服务
- Spring SimpleJdbcTemplate batchUpdate() example
- nmap扫描某段网络连通性
- python 将文件夹内的图片转换成PDF
- DAY6-小变化(java提示框)-2018-1-16
- centos下使用yum 安装pip
- windows驱动开发前导知识
- 「TJOI2015」组合数学 解题报告
- c++中static变量有什么用
- python之名称空间
- 【Docker江湖】之docker部署与理解
- Mysql 双主架构配置从复制
- Linux系统故障排查和修复技巧
- [BZOJ2733][HNOI2010]永无乡 解题报告 启发式合并,线段树合并
- Android的Message机制(简单小结)
- 2018-2019-2 20165332 《网络对抗技术》Exp4 恶意代码分析
热门文章
- UVA 1175 Ladies&#39; Choice 女士的选择(稳定婚姻问题,GS算法)
- Eclipse被卡死了或者失去响应了后分析根源的一个小技巧
- WEB前端研发工程师编程能力成长之路(2)(转)
- Python matlab octave 矩阵运算基础
- 阿里云ECS搭建node/mongodb开发环境及部署
- linux 搜索文本
- HDU-1297-Children’s Queue
- ubuntu16.04中将python3设置为默认+永久去除Ubuntu16.04报错
- React深入 - 手写redux api
- 南邮CTF--SQL注入题