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)


相关推荐

  • [深度学习] FM & FFM 算法基本原理

    [深度学习] FM & FFM 算法基本原理在推荐系统和计算广告业务中,点击率CTR(click-throughrate)和转化率CVR(conversionrate)是衡量流量转化的两个关键指标。准确的估计CTR、CVR对于提高流量的价值,增加广告及电商收入有重要的指导作用。无论使用什么类型的模型,点击率这个命题可以被归纳到二元分类的问题,我们通过单个个体的特征,计算出对于某个内容,是否点击了,点击了就是1,没点击就是0。对于任何二元分类的问题,最后我们都可以归结到逻辑回归上面。早期的人工特征工程+LR(Logisti…

  • jvisualvm 工具使用

    jvisualvm 工具使用转自:https://www.cnblogs.com/kongzhongqijing/articles/3625340.html jvisualvm工具使用 VisualVM是Netbeans的profile子项目,已在JDK6.0update7中自带(java启动时不需要特定参数,监控工具在bin/jvisualvm.exe)。&nbsp;https…

    2022年10月30日
  • golang 时间轮_窗口时间

    golang 时间轮_窗口时间timewheelGolang实现的时间轮,项目地址安装goget-ugithub.com/ouqiang/timewheel使用packagemainimport(“github.com/ouqiang/timewheel””time””fmt”)funcmain(){//tick刻度为1秒,3600个槽,执行的jobtw

  • Windows10下安装Oracle 11g

    Windows10下安装Oracle 11g一、下载Oracle官方下载地址:https://www.oracle.com/technetwork/database/enterprise-edition/downloads/index.html官网下载需要登陆Oracle账号,没有的可以注册一个。这里我分享一个百度云盘的下载链接(只有64位的):https://pan.baidu.com/s/1SV0CpCDew_lSVhISS…

  • 面向对象设计

    面向对象设计

    2021年11月28日
  • 新版Kubernetes问题处理流程

    新版Kubernetes问题处理流程

发表回复

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

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