给你N个数,有两种操作:
1:给区间[a,b]的所有数增加X
2:询问区间[a,b]的数的和。
第一行一个正整数n,接下来n行n个整数,
再接下来一个正整数Q,每行表示操作的个数,
如果第一个数是1,后接3个正整数,
表示在区间[a,b]内每个数增加X,如果是2,
表示操作2询问区间[a,b]的和是多少。
pascal选手请不要使用readln读入
对于每个询问输出一行一个答案
3
1
2
3
2
1 2 3 2
2 2 3
9
数据范围
1<=n<=200000
1<=q<=200000
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题目描述
如题,已知一个数列,你需要进行下面两种操作:
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的结果。
输入输出样例
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
11
8
20
说明
时空限制:1000ms,128M
数据规模:
对于30%的数据:N<=8,M<=10
对于70%的数据:N<=1000,M<=10000
对于100%的数据:N<=100000,M<=100000
(数据已经过加强^_^,保证在int64/long long数据范围内)
样例说明:
代码实现:
线段树练习 3:
#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;
LL n,m,a,b,c,d;
struct nate{LL l,r,s,flag;}t[];
void heritage(LL k){//标记传递。当使用某一区间时,把它的标记下传,并更改左右儿子的需求值。
LL lson=k*,rson=k*+;
t[lson].flag+=t[k].flag;
t[lson].s+=(t[lson].r-t[lson].l+)*t[k].flag;
t[rson].flag+=t[k].flag;
t[rson].s+=(t[rson].r-t[rson].l+)*t[k].flag;
t[k].flag=;
}
void make_tree(LL k,LL l,LL r){
LL lson=k*,rson=k*+;
t[k].l=l;t[k].r=r;
if(l==r){
scanf("%lld",&t[k].s);
return;
}
LL mid=(l+r)/;
make_tree(lson,l,mid);
make_tree(rson,mid+,r);
t[k].s=t[lson].s+t[rson].s;
}
void interval_change(LL k,LL l,LL r,LL v){
LL lson=k*,rson=k*+;
if(t[k].l==l&&t[k].r==r){
t[k].flag+=v;
t[k].s+=(t[k].r-t[k].l+)*v;
return;
}
if(t[k].flag) heritage(k);
LL mid=(t[k].l+t[k].r)/;
if(l<=mid) interval_change(lson,l,min(r,mid),v);
if(r>mid) interval_change(rson,max(l,mid+),r,v);
t[k].s=t[lson].s+t[rson].s;
}
LL interval_query(LL k,LL l,LL r){
LL lson=k*,rson=k*+;
if(t[k].l==l&&t[k].r==r) return t[k].s;
if(t[k].flag) heritage(k);
long long mid=(t[k].l+t[k].r)/,ans=;
if(l<=mid) ans+=interval_query(lson,l,min(r,mid));
if(r>mid) ans+=interval_query(rson,max(l,mid+),r);
return ans;
}
int main(){
scanf("%lld",&n);
make_tree(,,n);
scanf("%lld",&m);
for(int i=;i<=m;i++){
scanf("%lld",&a);
if(a==){
scanf("%lld%lld%lld",&b,&c,&d);
interval_change(,b,c,d);
}
if(a==){
scanf("%lld%lld",&b,&c);
printf("%lld\n",interval_query(,b,c));
}
}
return ;
}
【模板】线段树 1:
#include<cstdio>
#include<iostream>
using namespace std;
long long n,m,a,b,c,d;
struct nate{long long l,r,s,flag;}t[];
void heritage(long long k){
long long lson=k*,rson=k*+;
t[lson].flag+=t[k].flag;
t[lson].s+=(t[lson].r-t[lson].l+)*t[k].flag;
t[rson].flag+=t[k].flag;
t[rson].s+=(t[rson].r-t[rson].l+)*t[k].flag;
t[k].flag=;
}
void make_tree(long long k,long long l,long long r){
long long lson=k*,rson=k*+;
t[k].l=l;t[k].r=r;
if(l==r){
scanf("%lld",&t[k].s);
return;
}
long long mid=(l+r)/;
make_tree(lson,l,mid);
make_tree(rson,mid+,r);
t[k].s=t[lson].s+t[rson].s;
}
void interval_change(long long k,long long l,long long r,long long v){
long long lson=k*,rson=k*+;
if(t[k].l==l&&t[k].r==r){
t[k].flag+=v;
t[k].s+=(t[k].r-t[k].l+)*v;
return;
}
if(t[k].flag) heritage(k);
long long mid=(t[k].l+t[k].r)/;
if(l<=mid) interval_change(lson,l,min(r,mid),v);
if(r>mid) interval_change(rson,max(l,mid+),r,v);
t[k].s=t[lson].s+t[rson].s;
}
long long interval_query(long long k,long long l,long long r){
int lson=k*,rson=k*+;
if(t[k].l==l&&t[k].r==r) return t[k].s;
if(t[k].flag) heritage(k);
long long mid=(t[k].l+t[k].r)/,ans=;
if(l<=mid) ans+=interval_query(lson,l,min(r,mid));
if(r>mid) ans+=interval_query(rson,max(l,mid+),r);
return ans;
}
int main(){
scanf("%lld%lld",&n,&m);
make_tree(,,n);
for(int i=;i<=m;i++){
scanf("%lld",&a);
if(a==){
scanf("%lld%lld%lld",&b,&c,&d);
interval_change(,b,c,d);
}
if(a==){
scanf("%lld%lld",&b,&c);
printf("%lld\n",interval_query(,b,c));
}
}
return ;
}
其实两个题几乎一样,也是因为这个“几乎”,我洛谷上得了遍零分。
题目来源:CODE[VS],洛谷
线段树练习 3&&P3372 【模板】线段树 1的更多相关文章
-
【线段树】【P3372】模板-线段树
百度百科 Definition&Solution 线段树是一种log级别的树形结构,可以处理区间修改以及区间查询问题.期望情况下,复杂度为O(nlogn). 核心思想见百度百科,线段树即将每个 ...
-
hdu 1754 I Hate It (模板线段树)
http://acm.hdu.edu.cn/showproblem.php?pid=1754 I Hate It Time Limit: 9000/3000 MS (Java/Others) M ...
-
HDU 3966 Aragorn&#39;s Story(模板题)【树链剖分】+【线段树】
<题目链接> 题目大意: 给定一颗带点权的树,进行两种操作,一是给定树上一段路径,对其上每个点的点权增加或者减少一个数,二是对某个编号点的点权进行查询. 解题分析: 树链剖分的模板题,还不 ...
-
洛谷P3373 [模板]线段树 2(区间增减.乘 区间求和)
To 洛谷.3373 [模板]线段树2 题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.将某区间每一个数乘上x 3.求出某区间每一个数的和 输入输出格式 输入格 ...
-
洛谷 P3919 【模板】可持久化数组(可持久化线段树/平衡树)-可持久化线段树(单点更新,单点查询)
P3919 [模板]可持久化数组(可持久化线段树/平衡树) 题目背景 UPDATE : 最后一个点时间空间已经放大 标题即题意 有了可持久化数组,便可以实现很多衍生的可持久化功能(例如:可持久化并查集 ...
-
【BZOJ】1146: [CTSC2008]网络管理Network(树链剖分+线段树套平衡树+二分 / dfs序+树状数组+主席树)
http://www.lydsy.com/JudgeOnline/problem.php?id=1146 第一种做法(时间太感人): 第二种做法(rank5,好开心) ================ ...
-
【Hihocoder 1167】 高等理论计算机科学 (树链的交,线段树或树状数组维护区间和)
[题意] 时间限制:20000ms 单点时限:1000ms 内存限制:256MB 描述 少女幽香这几天正在学习高等理论计算机科学,然而她什么也没有学会,非常痛苦.所以她出去晃了一晃,做起了一些没什么意 ...
-
POJ 1804 Brainman(5种解法,好题,【暴力】,【归并排序】,【线段树单点更新】,【树状数组】,【平衡树】)
Brainman Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 10575 Accepted: 5489 Descrip ...
-
Vijos P1448 校门外的树【多解,线段树,树状数组,括号序列法+暴力优化】
校门外的树 描述 校门外有很多树,有苹果树,香蕉树,有会扔石头的,有可以吃掉补充体力的…… 如今学校决定在某个时刻在某一段种上一种树,保证任一时刻不会出现两段相同种类的树,现有两个操作: K=1,K= ...
-
【BZOJ3685】【zkw权值线段树】普通van Emde Boas树
原题传送门 因为马上要开始搞树套树了,所以学了一波权值线段树...毕竟是会点zkw线段树的,所以zkw线段树大法好! 解题思路: 介绍一下权值线段树吧,其实感觉就是线段树的本义,就是你用线段树维护了数 ...
随机推荐
-
HtmlPrefixScopeExtensions
http://blog.stevensanderson.com/2010/01/28/editing-a-variable-length-list-aspnet-mvc-2-style/
-
js获取fck值的代码方法
引入js文件 <script type="text/javascript" src="${basePath}/FCKeditor/fckeditor.js" ...
-
url 取出文件扩展名
/**url 取出文件扩展名 *///方法一function getExt1($url) { $arr = parse_url($url); $file = basename($arr[' ...
-
datagrid参数queryParams--easyUI
datagrid参数queryParams--easyUI Html <div region="center" border="false&qu ...
-
你所不了解的javascript操作DOM的细节知识点(一)
你所不了解的javascript操作DOM的细节知识点(一) 一:Node类型 DOM1级定义了一个Node接口,该接口是由DOM中的所有节点类型实现.每个节点都有一个nodeType属性,用于表明节 ...
-
LD_PRELOAD &; LD_LIBRARY_PATH 动态库路径
参考:http://www.cnblogs.com/waterlin/archive/2011/07/14/2106056.html 143上的glibc较低,同学又不能进行升级(造成全局影响),所以 ...
-
20165318 2017-2018-2 《Java程序设计》第九周学习总结
20165318 2017-2018-2 <Java程序设计>第九周学习总结 目录 学习过程遇到的问题及总结 教材学习内容总结 第13章 Java网络编程 代码托管 代码统计 学习过程遇到 ...
-
惭愧, eclipse 之 build path
算下来大学到现在已近用了很久的 eclipse 了, 包括 myeclipse, 但是今天碰到的问题让我很惭愧, 一个老项目的编译都搞了好久. 环境: Myeclipse 6.X Struts 1.X ...
-
.Net高级技术——对象序列化
对象序列化 “序列化是将一个对象保存到存储介质上或者将对象进行转换使之能够在网络上传送的行为”.通俗一点的解释,序列化就是把一个对象保存到一个文件或数据库字段中去,反序列化就是从文件或者数据库中取出数 ...
-
win10无法访问局域网共享文件?(因微软账户和本地账户登陆问题导致)
1 笔记本系统win10 X64企业版,其中一文件夹已设置为“共享”.本地帐号登录系统. 2 平板电脑系统win8.1 X64专业版,可以顺畅的访问笔记本的共享文件.微软帐号登录系统. 3 平板电脑系 ...