Description
给出了一个序列,你需要处理如下两种询问。
"C abc"表示给[a, b]区间中的值全部增加c (-10000 ≤ c ≤ 10000)。
"Q ab" 询问[a, b]区间中所有值的和。
Input
第一行包含两个整数N, Q。1≤ N,Q ≤ 100000.
第二行包含n个整数,表示初始的序列A (-1000000000 ≤ Ai ≤1000000000)。
接下来Q行询问,格式如题目描述。
Output
对于每一个Q开头的询问,你需要输出相应的答案,每个答案一行。
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15
依旧是线段树操作,注意数据范围用long long
//#include<bits/stdc++.h>//POJ不吃这条
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
struct NODE{
int l,r;
long long sum,t;
}node[];
int data[];
int n,m;
void Build(int num,int left,int right){//以num为根建线段树
node[num].l=left;
node[num].r=right;
if(left==right){
node[num].sum=data[left];
return;
}
int mid=(left+right)/;
Build(num*,left,mid);
Build(num*+,mid+,right);
node[num].sum=node[num*].sum+node[num*+].sum;
return;
} void update(int num){//标记下传
node[num<<].t+=node[num].t;
node[num*+].t+=node[num].t;
node[num<<].sum+=(node[num<<].r-node[num<<].l+)*node[num].t;
node[num*+].sum+=(node[num*+].r-node[num*+].l+)*node[num].t;
node[num].t=;
return;
}
long long qu(int l,int r,int num){//求和
if(node[num].r<l || node[num].l>r)return ;
if(node[num].l>=l && node[num].r<=r)return node[num].sum;
if(node[num].t)update(num);
return qu(l,r,num<<)+qu(l,r,num*+);
}
void change(int l,int r,int c,int num){
if(node[num].r<l || node[num].l>r)return;
if(node[num].l>=l && node[num].r<=r){
node[num].sum+=c*(node[num].r-node[num].l+);
node[num].t+=c;
return;
}
if(node[num].t)update(num);
change(l,r,c,num<<);
change(l,r,c,num*+);
node[num].sum=node[num<<].sum+node[num*+].sum;
return;
}
int main(){
scanf("%d%d",&n,&m);
int i,j;
for(i=;i<=n;i++)scanf("%d",&data[i]);
Build(,,n);
char s;
int a,b,c;
for(i=;i<=m;i++)
{
cin>>s;
if(s=='C'){
scanf("%d%d%d",&a,&b,&c);
change(a,b,c,);
}
if(s=='Q'){
scanf("%d%d",&a,&b);
printf("%lld\n",qu(a,b,));
}
}
return ;
}
因为printf里忘了用lld而WA,纠结了半个多小时才意识到问题所在←又犯了这种蠢错误
POJ3468 A Simple Problem with Integers的更多相关文章
-
线段树---poj3468 A Simple Problem with Integers:成段增减:区间求和
poj3468 A Simple Problem with Integers 题意:O(-1) 思路:O(-1) 线段树功能:update:成段增减 query:区间求和 Sample Input 1 ...
-
poj3468 A Simple Problem with Integers (线段树区间最大值)
A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 92127 ...
-
poj------(3468)A Simple Problem with Integers(区间更新)
A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 60745 ...
-
POJ3468 A Simple Problem with Integers 【段树】+【成段更新】
A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 57666 ...
-
poj3468 A Simple Problem with Integers (树状数组做法)
题目传送门 A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072K Total Submissions: 1 ...
-
POJ3468 A Simple Problem with Integers —— 线段树 区间修改
题目链接:https://vjudge.net/problem/POJ-3468 You have N integers, A1, A2, ... , AN. You need to deal wit ...
-
poj3468 A Simple Problem with Integers(线段树区间更新)
https://vjudge.net/problem/POJ-3468 线段树区间更新(lazy数组)模板题 #include<iostream> #include<cstdio&g ...
-
[POJ3468] A Simple Problem with Integers (Treap)
题目链接:http://poj.org/problem?id=3468 这题是线段树的题,拿来学习treap. 不旋转的treap. #include <cstdio> #include ...
-
POJ3468 A Simple Problem with Integers(线段树延时标记)
题目地址http://poj.org/problem?id=3468 题目大意很简单,有两个操作,一个 Q a, b 查询区间[a, b]的和 C a, b, c让区间[a, b] 的每一个数+c 第 ...
-
POJ-3468 A Simple Problem with Integers Splay Tree区间练习
题目链接:http://poj.org/problem?id=3468 以前用线段树做过,现在用Splay Tree A了,向HH.kuangbin.cxlove大牛学习了各种Splay各种操作,,, ...
随机推荐
-
Ubuntu 安装Samba服务器
1.安装 sudo apt-get update sudo apt-get install samba (如果出现库依赖问题可用命令sudo apt-get install samba libwbcl ...
-
TP收集一些可以用的资源
http://www.thinkphp.cn/code/2184.html UI http://www.thinkphp.cn/code/2158.html 报名 http://www.th ...
-
【C语言】zz优先队列的实现
做一个题目时,看见解法中使用了优先队列,http://hawstein.com/posts/3.6.html . 颇为好奇,找资料学习了一下,顺便做个摘要. c++的用法: 转自:http://blo ...
-
SqlSever基础 where 与 group by组合起来 处理数据
镇场诗:---大梦谁觉,水月中建博客.百千磨难,才知世事无常.---今持佛语,技术无量愿学.愿尽所学,铸一良心博客.------------------------------------------ ...
-
C语言每日一题之No.1
鉴于在学校弱弱的接触过C,基本上很少编程,C语言基础太薄弱.刚好目前从事的是软件编程,难度可想而知.严重影响工作效率,已无法再拖下去了.为此,痛下决心恶补C语言.此前只停留在看书,光看好像也记不住,C ...
-
z-index解决弹出层遮罩层覆盖子div不能显示输出的问题
// 添加以下代码来进行测试: // ajax 发生错误,就会执行$('body').ajaxError(function(e, xhr, setting, text){ // e - even ...
-
python编写网络抓包分析脚本
python编写网络抓包分析脚本 写网络抓包分析脚本,一个称手的sniffer工具是必不可少的,我习惯用Ethereal,简单,易用,基于winpcap的一个开源的软件 Ethereal自带许多协议的 ...
-
Elasticsearch 学习(二):安装和使用
一.安装 安装 Elasticsearch 之前,需要先安装 Java,并配置好 Java 环境变量. 安装好 Java 环境后,进入 Elasticsearch 官网下载安装包. 解压安装包,进入解 ...
-
Linux 进程管理工具 supervisord 安装及使用
Supervisor是用Python实现的一款非常实用的进程管理工具 1.安装过程非常简单 安装python 安装meld3-0.6.8.tar.gz 安装supervisor-3.0a12.tar. ...
-
Ubuntu 16.04安装Zabbix 3.2 版本
系统环境:ubuntu16.04 注意:为了便于实验测试,需要关闭防火墙: parallels@zabbix-server:~$ sudo systemctl stop ufw parallels ...