#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+50;
int t[2*N];
int query(int i){int ans=0;for(;i>0;i-=i&-i)ans+=t[i];return ans;}
void update(int i,int v){for(;i<N;i+=i&-i)t[i]+=v;}
int query(int l,int r){
if(l>r)return 0;
if(l==0)return query(r);
return query(r)-query(l-1);
}
signed main(){
int n,k;
cin>>n>>k;
int a[n+1];
for(int i=1;i<=n;i++)cin>>a[i];
int pref[n+1];
pref[0]=0;
for(int i=1;i<=n;i++)pref[i]=pref[i-1]+a[i];
int q;
cin>>q;
if(max(n,q)<=10000&&k==1){
while(q--){
int o;
cin>>o;
if(o==1){
int X;
cin>>X;
continue;
}
int l,r,m;
cin>>l>>r>>m;
int ans=0;
// i>r-m+1
//for(int i=l;i<=r-m+1;i++)ans+=pref[i+m-1]-pref[i-1];.
for(int i=r;i>=l+m-1;i--){
ans+=pref[i];
}
for(int i=l-1;i<=r-m;i++)ans-=pref[i];
cout<<ans;
cout<<endl;
}
return 0;
}
if(k==1){
for(int i=1;i<=n;i++)update(i,pref[i]);
while(q--){
int o;
cin>>o;
if(o==1){
int X;
cin>>X;
continue;
}
int l,r,m;
cin>>l>>r>>m;
int ans=query(l+m-1,r);
ans-=query(l-1,r-m);
cout<<ans;
cout<<endl;
}
}
}
/*
8 1
7 2 5 1 9 3 4 6
1
2 2 7 4
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
2 ms |
348 KB |
Output is correct |
3 |
Correct |
7 ms |
348 KB |
Output is correct |
4 |
Correct |
9 ms |
348 KB |
Output is correct |
5 |
Correct |
13 ms |
348 KB |
Output is correct |
6 |
Correct |
18 ms |
348 KB |
Output is correct |
7 |
Correct |
23 ms |
412 KB |
Output is correct |
8 |
Correct |
29 ms |
576 KB |
Output is correct |
9 |
Correct |
51 ms |
600 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
42 ms |
1116 KB |
Output is correct |
2 |
Correct |
61 ms |
2136 KB |
Output is correct |
3 |
Correct |
82 ms |
2896 KB |
Output is correct |
4 |
Correct |
150 ms |
4696 KB |
Output is correct |
5 |
Correct |
213 ms |
6760 KB |
Output is correct |
6 |
Correct |
194 ms |
6428 KB |
Output is correct |
7 |
Correct |
192 ms |
6428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
12 ms |
1076 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |