Simple Problem with Integers POJ – 3468

Simple Problem with Integers POJ – 3468

你有N整数,A1, A2, … , AN..你需要处理两种操作。一种操作是在给定的时间间隔内向每个数字添加一些给定的数字。另一种是要求给定区间内的数字之和。

输入

第一行包含两个数字NQ..1≤N,Q≤100000。
第二行包含N的初始值A1, A2, … , AN..-1000000000≤Ai≤1000000000。
下一个Q行表示操作。
“Ca b c“意思是增加c每一个AaAa+1, … , Ab..-10000≤c≤10000。
“Qa b“意思是查询…之和。AaAa+1, … , Ab.

输出量

你需要回答所有Q命令有条不紊。一字一句地回答。

样本输入

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

样本输出

4
55
9
15

这道题也是个裸题,主要知识点,懒人标记入门 区间修改,区间查询。

上代码

 

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#define LL long long
using namespace std;
const int MAX = 50000 + 10;
long long tree[MAX*4], lz[MAX*4],len[MAX];
void init(){
    memset(tree,0,sizeof(tree));
    memset(lz,0,sizeof(lz));
}
 //建树成功! 
void build(int node, int l,int r)
{
    len[node]=r-l+1;
    if(l==r)
    {
        cin>>tree[node];
        return ;
    }
    int mid=(l+r)/2;
    build(2*node,l,mid);
    build(2*node+1,mid+1,r);
    tree[node]=tree[2*node]+tree[2*node+1];
}
//ok! gaizhi1chenghgong
void push_down(int node){
    if(lz[node]){
        lz[node*2] += lz[node];
        lz[node*2 + 1] += lz[node];
        // 注意线段树的数据更新方式要一致
        tree[node*2] += len[node*2]*lz[node];
        tree[node*2 + 1] += len[node*2+1]*lz[node];
        lz[node] = 0;
    }
}
void update_range(int node,int l,int r,int L,int R,int add){
    if(l <= L && r >= R){
        lz[node] += 1LL*add;
        tree[node] += 1LL*(R - L + 1)*add; // 更新方式
        return;
    }
    push_down(node);
    int mid = (L+R) / 2;
    if(mid >= l) update_range(node*2,l,r,L,mid,add);
    if(mid < r) update_range(node*2 + 1,l,r,mid+1,R,add);
    tree[node] = tree[node*2] + tree[node*2 + 1];
}
long long query(int l,int r,int node,int x, int y)
{
    if(x<=l&&y>=r)
        return tree[node];
    push_down(node);
    int mid=(l+r)/2;
    int sum=0;
    if(mid>=x){
        sum=sum+query( l, mid, node*2, x, y);
    }
    if(mid<y)//chadiancuol
    {    
    sum=sum+query( mid+1, r, node*2+1, x, y);
    }
    return sum;
}
int main()
{
    int m,n;
    init();
    char s[MAX];
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        build(1,1,m);
        int x, y,z;
        
        while(n--)
        {
            scanf("%s",s);
            if(s[0]=='Q')
            {
                scanf("%d %d",&x,&y);
                printf("%lld\n",query(1,m,1,x,y));
            }
            if(s[0]=='C')
            {
                scanf("%d %d %d",&x,&y,&z);
                update_range(1,1,m,x,y,z);
            }
        }
    }    
    return 0;
}

回去发现又错误,检查了将近两小时,才发现,更新区域的值函数,形式参数为小写的了l,r,然后与大写的搞混了。

这样的情况已经不是第一次发生了,找这种错误耗费了我太多无用功,

下次如果再有超过半小时还没找出错误的,感觉思路绝对没问题,就自己重新写,然后就是函数的形式参数的名字尽量要区分开,找的要猝死了,感觉啊。。。

void update_range(int l,int r,int node,int L,int R,int add){
    if(L <=l  && R >= r){
        lz[node] += add;
        tree[node] += len[node]*add; // 
        return;
    }
    push_down(node);
    int mid = (l+r) / 2;
    if(mid >= L) update_range(l,mid,node*2,L,R,add);
    if(mid < R) update_range(mid+1,r,node*2+1,L,R,add);//就错这里,,,,,
    tree[node] = tree[node*2] + tree[node*2 + 1];
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。

发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/114887.html原文链接:https://javaforall.net

(0)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • eclipse没有server选项怎么解决

    eclipse是一个开放源代码的、基于java的可扩展开发平台。它使用频率十分高,然而当使用它部署项目时候,经常会发现一个重要的问题就是打开eclipse之后没有了server选项,那么该怎么解决这个问题呢?第一步、在eclipse菜单“Help”中选择“InstallNewSoftware”第二步、在浏览器输入:https://download.eclipse….

    2022年4月7日
    50
  • 什么是JavaBean、bean? 什么是POJO、PO、DTO、VO、BO ? 什么是EJB、EntityBean?

    什么是JavaBean、bean? 什么是POJO、PO、DTO、VO、BO ? 什么是EJB、EntityBean?前言:在Java开发中经常遇到这些概念问题,有的可能理解混淆,有的可能理解不到位,特此花了很多时间理顺了这些概念。不过有些概念实际开发中并没有使用到,可能理解还不够准确,只能靠后续不断纠正了。1、什么是POJO?POJO(PlainOldJavaObject)这种叫法是MartinFowler、RebeccaParsons和JoshMacKenzie在2000年的一…

    2022年5月28日
    67
  • Ubuntu终端打开文件及查看目录「建议收藏」

    Ubuntu终端打开文件及查看目录「建议收藏」方法/步骤 1ctrl+alt+t,调出终端。———— 要去某个目录,用cd 例如:cd/home/yang/下载/ 在视图中,后面还有一个文件夹,我记不住,就按tab键一下。就自动出来了。 如果该文件夹下东西比较多,你记不住,那就多按两次tab,就会出现可以进入的文件夹。在这里我要进入【下载】文件夹里。————- …

    2022年10月11日
    2
  • linux添加防火墙规则_linux如何查看防火墙状态

    linux添加防火墙规则_linux如何查看防火墙状态linux防火墙对于我们来说是非常重要的!那么我们要怎么样去配置呢?下面由学习啦小编给你做出详细的linux防火墙配置方法介绍!希望对你有帮助!linux防火墙配置方法一:1./sbin/iptables-AINPUT-ptcp–dport80-jACCEPT2./sbin/iptables-AINPUT-ptcp–dport25-jACCEPT3.ech…

    2022年9月15日
    2
  • H2内存数据库的函数「建议收藏」

    每个数据库为了使用者的查询简便性以及使用效率,都有专门提供一些函数给使用者进行使用,H2也同样如此,虽然没有oracle那么多强大的函数,但是一般需求的使用还是能够满足,下面就简单介绍下都有哪些函数一、函数的分类以及名称1、聚合函数(AggregateFunctions) AVGBOOL_ANDBOOL_ORCOUNTGROUP_CONCAT MAXMIN…

    2022年4月15日
    37

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号