POJ3468 A Simple Problem with Integers

时间:2022-08-28 11:53:50

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的更多相关文章

  1. 线段树---poj3468 A Simple Problem with Integers&colon;成段增减&colon;区间求和

    poj3468 A Simple Problem with Integers 题意:O(-1) 思路:O(-1) 线段树功能:update:成段增减 query:区间求和 Sample Input 1 ...

  2. poj3468 A Simple Problem with Integers &lpar;线段树区间最大值&rpar;

    A Simple Problem with Integers Time Limit: 5000MS   Memory Limit: 131072K Total Submissions: 92127   ...

  3. poj------&lpar;3468&rpar;A Simple Problem with Integers&lpar;区间更新&rpar;

    A Simple Problem with Integers Time Limit: 5000MS   Memory Limit: 131072K Total Submissions: 60745   ...

  4. POJ3468 A Simple Problem with Integers 【段树】&plus;【成段更新】

    A Simple Problem with Integers Time Limit: 5000MS   Memory Limit: 131072K Total Submissions: 57666   ...

  5. poj3468 A Simple Problem with Integers (树状数组做法)

    题目传送门 A Simple Problem with Integers Time Limit: 5000MS   Memory Limit: 131072K Total Submissions: 1 ...

  6. POJ3468 A Simple Problem with Integers —— 线段树 区间修改

    题目链接:https://vjudge.net/problem/POJ-3468 You have N integers, A1, A2, ... , AN. You need to deal wit ...

  7. poj3468 A Simple Problem with Integers(线段树区间更新)

    https://vjudge.net/problem/POJ-3468 线段树区间更新(lazy数组)模板题 #include<iostream> #include<cstdio&g ...

  8. &lbrack;POJ3468&rsqb; A Simple Problem with Integers &lpar;Treap&rpar;

    题目链接:http://poj.org/problem?id=3468 这题是线段树的题,拿来学习treap. 不旋转的treap. #include <cstdio> #include ...

  9. POJ3468 A Simple Problem with Integers&lpar;线段树延时标记&rpar;

    题目地址http://poj.org/problem?id=3468 题目大意很简单,有两个操作,一个 Q a, b 查询区间[a, b]的和 C a, b, c让区间[a, b] 的每一个数+c 第 ...

  10. POJ-3468 A Simple Problem with Integers Splay Tree区间练习

    题目链接:http://poj.org/problem?id=3468 以前用线段树做过,现在用Splay Tree A了,向HH.kuangbin.cxlove大牛学习了各种Splay各种操作,,, ...

随机推荐

  1. Ubuntu 安装Samba服务器

    1.安装 sudo apt-get update sudo apt-get install samba (如果出现库依赖问题可用命令sudo apt-get install samba libwbcl ...

  2. TP收集一些可以用的资源

    http://www.thinkphp.cn/code/2184.html    UI http://www.thinkphp.cn/code/2158.html   报名 http://www.th ...

  3. 【C语言】zz优先队列的实现

    做一个题目时,看见解法中使用了优先队列,http://hawstein.com/posts/3.6.html . 颇为好奇,找资料学习了一下,顺便做个摘要. c++的用法: 转自:http://blo ...

  4. SqlSever基础 where 与 group by组合起来 处理数据

    镇场诗:---大梦谁觉,水月中建博客.百千磨难,才知世事无常.---今持佛语,技术无量愿学.愿尽所学,铸一良心博客.------------------------------------------ ...

  5. C语言每日一题之No&period;1

    鉴于在学校弱弱的接触过C,基本上很少编程,C语言基础太薄弱.刚好目前从事的是软件编程,难度可想而知.严重影响工作效率,已无法再拖下去了.为此,痛下决心恶补C语言.此前只停留在看书,光看好像也记不住,C ...

  6. z-index解决弹出层遮罩层覆盖子div不能显示输出的问题

    // 添加以下代码来进行测试: // ajax 发生错误,就会执行$('body').ajaxError(function(e, xhr, setting, text){    // e - even ...

  7. python编写网络抓包分析脚本

    python编写网络抓包分析脚本 写网络抓包分析脚本,一个称手的sniffer工具是必不可少的,我习惯用Ethereal,简单,易用,基于winpcap的一个开源的软件 Ethereal自带许多协议的 ...

  8. Elasticsearch 学习(二):安装和使用

    一.安装 安装 Elasticsearch 之前,需要先安装 Java,并配置好 Java 环境变量. 安装好 Java 环境后,进入 Elasticsearch 官网下载安装包. 解压安装包,进入解 ...

  9. Linux 进程管理工具 supervisord 安装及使用

    Supervisor是用Python实现的一款非常实用的进程管理工具 1.安装过程非常简单 安装python 安装meld3-0.6.8.tar.gz 安装supervisor-3.0a12.tar. ...

  10. Ubuntu 16&period;04安装Zabbix 3&period;2 版本

    系统环境:ubuntu16.04 注意:为了便于实验测试,需要关闭防火墙: parallels@zabbix-server:~$ sudo systemctl stop ufw   parallels ...