ACM-ICPC 2018 徐州赛区网络预赛 - H Ryuji doesn't want to study - 线段树
程序员文章站
2022-03-21 07:51:06
...
思路:
维护两个线段树,第一个是普通的区间和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);
}
}
}
上一篇: 洛谷 校门外的树
下一篇: Kuangbin专题七线段树
推荐阅读
-
【计蒜客】2018ICPC徐州赛区网络赛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(线段树区间求和)
-
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 - 线段树