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

ACM-ICPC 2018 徐州赛区网络预赛 - H Ryuji doesn't want to study - 线段树

程序员文章站 2022-03-21 07:51:06
...

ACM-ICPC 2018 徐州赛区网络预赛 - H Ryuji doesn't want to study - 线段树

ACM-ICPC 2018 徐州赛区网络预赛 - H Ryuji doesn't want to study - 线段树

ACM-ICPC 2018 徐州赛区网络预赛 - H Ryuji doesn't want to study - 线段树

思路:

维护两个线段树,第一个是普通的区间和sum,第二个是,把每个值变成A[l]*(n-l+1),求区间和sum1

比如1 3 4 2,第二个线段树的A值看成1*4,3*3,4*2,2*1

在询问一个区间时,我们发现所求得结果正好是:sum1[b,c]-(n-c)*sum[b,c]

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<string>
#include<cstring>
using namespace std;
#define ll long long
#define lson l,m,k<<1
#define rson m+1,r,k<<1|1
const int N=100005;
ll sum[N<<2],sum1[N<<2];
int n;ll A[N];
void build(int l,int r,int k){
    if(l==r){
        sum[k]=A[l];
        sum1[k]=A[l]*(n-l+1);
        return ;
    }
    int m=(l+r)>>1;
    build(lson);
    build(rson);
    sum[k]=sum[k<<1]+sum[k<<1|1];
    sum1[k]=sum1[k<<1]+sum1[k<<1|1];
}
ll query(int L,int R,int l,int r,int k,ll ss[]){
    if(L<=l&&R>=r)return ss[k];
    int m=(l+r)>>1;
    ll ans=0;
    if(L<=m)ans+=query(L,R,lson,ss);
    if(R>m)ans+=query(L,R,rson,ss);
    return ans;
}

void update(int P,ll N,int l,int r,int k){
    if(l==r){
        sum[k]=N;
        sum1[k]=N*(n-l+1);
        return ;
    }
    int m=(l+r)>>1;
    if(P<=m)update(P,N,lson);
    else update(P,N,rson);
    sum[k]=sum[k<<1]+sum[k<<1|1];
    sum1[k]=sum1[k<<1]+sum1[k<<1|1];
}

int main(){
    int q;
    int a,b,c;
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)scanf("%lld",&A[i]);
    build(1,n,1);
    while(q--){
        scanf("%d",&a);
        if(a==1){
            scanf("%d%d",&b,&c);
            ll ans=query(b,c,1,n,1,sum1);
            ans=ans-(n-c)*query(b,c,1,n,1,sum);
            printf("%lld\n",ans);
        }
        else{
            ll x;
            scanf("%d%lld",&b,&x);
            update(b,x,1,n,1);
        }
    }
}

 

相关标签: 线段树