This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
long long pre[100005];
long long n,k;
long long b1[100005],b2[100005];
void update(long long bit[], long long v, long long x){
while(v<=n){
bit[v]+=x;
v+=v&(-v);
}
}
void up(long long l, long long r, long long x){
update(b1, l, x);
update(b1, r+1, -x);
update(b2, l, (l-1)*x);
update(b2, r+1, -r*x);
}
long long presum(long long bit[], long long v){
long long s=0;
while(v>0){
s+=bit[v];
v-=v&(-v);
}
return s;
}
long long sum(long long l,long long r){
return presum(b1, r)*r-presum(b2, r)-(presum(b1, l-1)*(l-1)-presum(b2, l-1));
}
int main(){
cin>>n>>k;
long long a[n+1];
long long prefix=0;
for(long long i=1; i<=n; i++){
cin>>a[i];
prefix+=a[i];
up(i,i,prefix);
}
long long q;
cin>>q;
while(q--){
long long x;
cin>>x;
if(x==1){
long long b[k+1];
for(long long i=1; i<=k; i++){
cin>>b[i];
}
up(b[k],n,a[b[1]]-a[b[k]]);
for(long long i=1; i<k; i++){
up(b[i],n, a[b[i+1]]-a[b[i]] );
}
continue;
}
long long l,r,m;
cin>>l>>r>>m;
long long s=0;
s+=sum(l+m-1, r);
s-=sum(l-1, r-m);
cout<<s<<endl;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |