A Simple Problem with Integers

题目链接

http://poj.org/problem?id=3468

解题思路

区间修改,区间查询

AC代码

//我服了,不都开ll居然wa???要数据规模啥用???(或许wtcl,debug4小时!!!)
#include<algorithm>
#include<cstdio>
#define ll long long
using namespace std;

const int N=1e6+10;
struct TREE
{
    ll l,r,lazy;
    ll sum;    
}tree[N];
ll n,m,x,y;
ll cc;
ll a[N];
char op;
void Build(int i,ll l,ll r)
{
    tree[i].l=l;
    tree[i].r=r;
    tree[i].sum=0;
    tree[i].lazy=0;
    if(l==r)
    {
        tree[i].sum=a[l];
        return ;
    }
    ll mid=(l+r)>>1;
    Build(i<<1,l,mid);//left
    Build(i<<1|1,mid+1,r);//right
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    return ;
}
void PushDown(int i)
{
    if(tree[i].lazy==0) return ;
    tree[i<<1].lazy+=tree[i].lazy;//left//注意是+=
    tree[i<<1|1].lazy+=tree[i].lazy;//right//注意是+=
    tree[i<<1].sum+=tree[i].lazy*(tree[i<<1].r-tree[i<<1].l+1);//left//注意是+=
    tree[i<<1|1].sum+=tree[i].lazy*(tree[i<<1|1].r-tree[i<<1|1].l+1);//right//注意是+=
    tree[i].lazy=0;
    return ;
}
void Update(int i,ll l,ll r,ll c)
{
    if(tree[i].l>r||tree[i].r<l) return;
    if(l<=tree[i].l && tree[i].r<=r)
    {
        tree[i].lazy+=c;//注意是+=
        tree[i].sum+=c*(tree[i].r-tree[i].l+1);//注意是+=
        return ;
    }
    PushDown(i);
    if(tree[i<<1].r>=l) Update(i<<1,l,r,c);
    if(tree[i<<1|1].l<=r) Update(i<<1|1,l,r,c);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    return ;
}
ll Query(int i,ll l,ll r)
{

    if(l<=tree[i].l && tree[i].r<=r)
    return tree[i].sum;
    if(tree[i].l>r || tree[i].r<l) return 0;
    PushDown(i);
    ll res=0;
    if(tree[i<<1].r>=l) res+=Query(i<<1,l,r);
    if(tree[i<<1|1].l<=r) res+=Query(i<<1|1,l,r);
    tree[i].sum=tree[i<<1].sum+tree[i<<1|1].sum;
    return res;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    Build(1,1,n);
    while(m--)
    {
        getchar();//注意
        scanf("%c",&op);
        if(op=='C')
        {
            scanf("%lld%lld%lld",&x,&y,&cc);
            Update(1,x,y,cc);
        }
        else 
        {
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",Query(1,x,y));
        }
    } 

    return 0;
}
线段树 文章被收录于专栏

菜鸡随便搞一波

全部评论

相关推荐

01-23 14:54
同济大学 Java
热爱敲代码的程序媛:给你提几点【专业技能】这个模块里面可优化的地方:1.【具备JVM调优经验】可以去b站上搜一下JVM调优的视频,估计一两个小时凭你的学习能力就能掌握JVM调优的实践方面的技能。2.【MySql优化】MySql这一栏,你去b站或者找个博客看看MySql优化,学一下,如果你本身比较熟悉MySql语句的话,那基本半天时间凭你的学习能力MySql语句优化方面的技能你也能掌握个差不多。以上1,2两点主要是因为我看你专业技能大部分都说的是偏理论,没有写应用。再就是最后,你结合你的项目,想一想你的项目中哪些sql语句是可以用MySql优化的,到时候你面试的时候也好结合着说一下。
点赞 评论 收藏
分享
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务