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];
}

 

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

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

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • MFCC算法讲解及实现(matlab)[通俗易懂]

    MFCC算法讲解及实现(matlab)[通俗易懂]史上最详细的MFCC算法实现(附测试数据)1.matlab安装voicebox语音包2.MFCC原理讲解3.MFCC算法设计实现(matlab)3.1.wav格式语音文件提取【x(200000*1)】3.2预加重【x(200000*1)】3.3分帧{S(301*1103)}3.4加窗{C(301*1103)}3.5傅里叶变换3.6梅尔滤波器3.7离散余弦变换4.1.matlab安装…

  • BZOJ2803[Poi2012]Prefixuffix——hash

    BZOJ2803[Poi2012]Prefixuffix——hash

  • IntelliJ IDEA创建Servlet最新方法 Idea版本2020.2.2以及IntelliJ IDEA创建Servlet 404问题(超详细)

    IntelliJ IDEA创建Servlet最新方法 Idea版本2020.2.2以及IntelliJ IDEA创建Servlet 404问题(超详细)第一次用IntelliJIDEA写java代码,之前都是用eclipse,但eclipse太老了。下面为兄弟们奉上IntelliJIDEA创建Servlet方法,写这个的目的也是因为在网上找了很多资料但都过时了,所以把我走过的坑和弯路直接告诉兄弟们,为大家节省点宝贵的时间。说一下现在创建Servlet或者是web和之前的主要区别,之前是直接创建,现在是先要创建java项目然后通过添加支持框架变成Servlet或者web项目下面这些截图最好都看完,因为有的地方有坑,都在后面的截图里。我用

  • TCP报文段格式[通俗易懂]

    三次握手就是一次TCP建立链接的过程四次挥手就是一次TCP断开的过程所以在学习三次握手四次挥手之前先了解一下TCP报文段的格式源端口(2字节):发送端应用程序的端口号,与源IP地址确定一个唯一地址目的端口(2字节):接收端计算机应用程序的端口号,与目的IP地址确定唯一的地址序号(4字节):TCP是面向字节流传输的,他为每一个字节编了一个序号,该报文段中序号为传输数据第一个字节的序号,例如:一个报文…

  • Apifox(2)快速上手apifox

    Apifox(2)快速上手apifox快速上手使用场景Apifox是接口管理、开发、测试全流程集成工具,使用受众为整个研发技术团队,主要使用者为前端开发、后端开发和测试人员。前端开发接口文档管理接口数据Mock接口调试前

  • Codeforces Round #243 (Div. 2) Problem B – Sereja and Mirroring 解读

    Codeforces Round #243 (Div. 2) Problem B – Sereja and Mirroring 解读

发表回复

您的电子邮箱地址不会被公开。

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