正文

线段树练习 3&&P3372 【模板】线段树 1

IP云
IP云V管理员/5 阅读
08/23
小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序
题目描述 Description

给你N个数，有两种操作：

1：给区间[a,b]的所有数增加X

2：询问区间[a,b]的数的和。

输入描述 Input Description

第一行一个正整数n，接下来n行n个整数，

再接下来一个正整数Q，每行表示操作的个数，

如果第一个数是1，后接3个正整数，

表示在区间[a,b]内每个数增加X,如果是2，

表示操作2询问区间[a,b]的和是多少。

pascal选手请不要使用readln读入

输出描述 Output Description

对于每个询问输出一行一个答案

样例输入 Sample Input

3

1

2

3

2

1 2 3 2

2 2 3

样例输出 Sample Output

9

数据范围及提示 Data Size & Hint

数据范围

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的结果。

输入输出样例

输入样例#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数据范围内）

样例说明：

代码实现：

线段树练习 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的更多相关文章

  1. 【线段树】【P3372】模板-线段树

    百度百科 Definition&Solution 线段树是一种log级别的树形结构,可以处理区间修改以及区间查询问题.期望情况下,复杂度为O(nlogn). 核心思想见百度百科,线段树即将每个 ...

  2. hdu 1754 I Hate It &lpar;模板线段树&rpar;

    http://acm.hdu.edu.cn/showproblem.php?pid=1754 I Hate It Time Limit: 9000/3000 MS (Java/Others)    M ...

  3. HDU 3966 Aragorn&&num;39&semi;s Story&lpar;模板题&rpar;【树链剖分】&plus;【线段树】

    <题目链接> 题目大意: 给定一颗带点权的树,进行两种操作,一是给定树上一段路径,对其上每个点的点权增加或者减少一个数,二是对某个编号点的点权进行查询. 解题分析: 树链剖分的模板题,还不 ...

  4. 洛谷P3373 &lbrack;模板&rsqb;线段树 2&lpar;区间增减&period;乘 区间求和&rpar;

    To 洛谷.3373 [模板]线段树2 题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某区间每一个数加上x 2.将某区间每一个数乘上x 3.求出某区间每一个数的和 输入输出格式 输入格 ...

  5. 洛谷 P3919 【模板】可持久化数组（可持久化线段树&sol;平衡树）-可持久化线段树&lpar;单点更新，单点查询&rpar;

    P3919 [模板]可持久化数组(可持久化线段树/平衡树) 题目背景 UPDATE : 最后一个点时间空间已经放大 标题即题意 有了可持久化数组,便可以实现很多衍生的可持久化功能(例如:可持久化并查集 ...

  6. 【BZOJ】1146&colon; &lbrack;CTSC2008&rsqb;网络管理Network（树链剖分&plus;线段树套平衡树&plus;二分 &sol; dfs序&plus;树状数组&plus;主席树）

    http://www.lydsy.com/JudgeOnline/problem.php?id=1146 第一种做法(时间太感人): 第二种做法(rank5,好开心) ================ ...

  7. 【Hihocoder 1167】 高等理论计算机科学 （树链的交，线段树或树状数组维护区间和）

    [题意] 时间限制:20000ms 单点时限:1000ms 内存限制:256MB 描述 少女幽香这几天正在学习高等理论计算机科学,然而她什么也没有学会,非常痛苦.所以她出去晃了一晃,做起了一些没什么意 ...

  8. POJ 1804 Brainman&lpar;5种解法，好题，【暴力】，【归并排序】，【线段树单点更新】，【树状数组】，【平衡树】&rpar;

    Brainman Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 10575   Accepted: 5489 Descrip ...

  9. Vijos P1448 校门外的树【多解，线段树，树状数组，括号序列法&plus;暴力优化】

    校门外的树 描述 校门外有很多树,有苹果树,香蕉树,有会扔石头的,有可以吃掉补充体力的…… 如今学校决定在某个时刻在某一段种上一种树,保证任一时刻不会出现两段相同种类的树,现有两个操作: K=1,K= ...

  10. 【BZOJ3685】【zkw权值线段树】普通van Emde Boas树

    原题传送门 因为马上要开始搞树套树了,所以学了一波权值线段树...毕竟是会点zkw线段树的,所以zkw线段树大法好! 解题思路: 介绍一下权值线段树吧,其实感觉就是线段树的本义,就是你用线段树维护了数 ...

随机推荐

  1. 深入理解CSS过渡transition

    × 目录 [1]定义 [2]过渡属性 [3]持续时间[4]延迟时间[5]时间函数[6]多值[7]阶段[8]触发[9]API 前面的话 通过过渡transition,可以让web前端开发人员不需要jav ...

  2. failover机制的小讨论

    对于一个7*24小时无间断的线上服务来说,在服役时间内难免会遇到一些fail,例如db断开连接且短暂连接不上了, 下游的某个节点忽然挂了,运维部署上依赖的某一个东西不存在了等等场景.本文主要来讨论一下 ...

  3. Asp&period;net 主题 【2】

    通常我们经常看到网页,一些软件提供换肤功能,各种主题间切换.ASP.NET 2.0 中可以用Theme和skin以及CSS轻松实现这个功能. 首先简单介绍一下三种技术:主题(Theme)技术,面板(s ...

  4. JSP通过SmartUpload上传文件实例

    httpRequest.setCharacterEncoding("gbk"); String preName = genName.doMake();//设置文件前缀名 Strin ...

  5. part1

    一.hello world 明确的指出 hello.py 脚本由 python 解释器来执行.coding:utf-8处理脚本中的中文 #!/usr/bin/env python # _*_ codi ...

  6. vuex最简单的

    https://segmentfault.com/a/1190000009404727 "dependencies": {    "axios": " ...

  7. 查询某个SPID，session&lowbar;id对应的执行sql&period;

    select er.session_id, CAST(csql.text AS varchar(255)) AS CallingSQL from master.sys.dm_exec_requests ...

  8. DataGridView控件使用大全说明-各种常用操作与高级操作

    DataGridView控件 DataGridView是用于Windows Froms 2.0的新网格控件.它可以取代先前版本中DataGrid控件,它易于使用并高度可定制,支持很多我们的用户需要的特 ...

  9. python3 enumerate&lpar;&rpar;函数笔记

    d={"A":"a","B":"b","C":"c","D" ...

  10. yii2下的路由重写

    1.在config/main.php中添加配置信息 文件位置如图所示(图中展示的是backend下的config,也可以在fronted和common的config中添加) 配置的代码标准格式如下 ' ...