欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study(线段树区间求和)

程序员文章站 2022-07-13 11:18:50
...

题目链接:https://nanti.jisuanke.com/t/31460

ACM-ICPC 2018 徐州赛区网络预赛 H. Ryuji doesn't want to study(线段树区间求和)

 

样例输入 
5 3
1 2 3 4 5
1 1 3
2 5 0
1 4 5
样例输出 
10
8

题意:n长的数列,q个询问,1操作表示输出l到r (r-l+1)*a[l]+(r-l)*a[l-1]+……+a[r]的和 ,2表示将a[l]更新为r

思路:线段树原数组为a的前缀和数组,那么a[l]更新为r只需要在[l,n]区间,都加上(r-更新前的值)就好了,要更新原数组a[l]=r,因为一个点可能会重复更新。求和,可以发现,需要求的答案=前缀和区间[l,r]的和,减去(r-l+1)*presum[l-1],而这个减去的部分也需要用区间求和来得到,而不能直接用presum[l-1],因为会有延迟更新的存在。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#define maxn 100005
#define lson rt<<1
#define rson rt<<1|1
using namespace std;
typedef long long ll;
ll tree[maxn<<2],add[maxn<<2];
ll a[maxn],presum[maxn];
int n,q;
void build(int rt,int l,int r){
    add[rt]=0;
    if(l==r){
        tree[rt]=presum[l];
    } else {
        int m=l+r>>1;
        build(rt<<1,l,m);
        build(rt<<1|1,m+1,r);
        tree[rt]=tree[lson]+tree[rson];
    }
}

void PushDown(int rt,int l,int r){
    int m=(l+r)/2;
    tree[lson]+=add[rt]*(m-l+1);
     add[lson]+=add[rt];
    tree[rson]+=add[rt]*(r-(m+1)+1);
     add[rson]+=add[rt];
    add[rt]=0;
}

ll query(int rt,int l,int r,int L,int R)
{
    if(r<L||R<l)return 0;
    else if(L<=l&&r<=R)return tree[rt];
    PushDown(rt,l,r);
    int m=l+r>>1;
    return query(lson,l,m,L,R)+query(rson,m+1,r,L,R);
}

void update(int rt,int l,int r,ll v,int L,int R)
{
    if(r<L||R<l)return ;
    else if(L<=l&&r<=R){
        add[rt]+=v;
        tree[rt]+=v*(r-l+1);
        return ;
    }
    PushDown(rt,l,r);
    int m=l+r>>1;
    update(lson,l,m,v,L,R);
    update(rson,m+1,r,v,L,R);
    tree[rt]=tree[lson]+tree[rson];
}

int main(){
    scanf("%d%d",&n,&q);
    presum[0]=0;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        presum[i]=presum[i-1]+a[i];
    }
    build(1,1,n);
    while(q--){
        int op,l,r;
        scanf("%d%d%d",&op,&l,&r);
        if(op==1){
            ll ans=query(1,1,n,l,r);
            if(l!=1)ans-=(r-l+1)*query(1,1,n,l-1,l-1);
            printf("%lld\n",ans);

        }
		else{
            update(1,1,n,r-a[l],l,n);
            a[l]=r;
        }
    }
    return 0;
}