#include<bits/stdc++.h>
using namespace std;
long long n,k,a[100009],pref[100009],pref2[100009],pref3[100009],type,l,r,m,siz,z,cnt;
void update(long long ind,long long maxind,long long a,long long b,long long fenvik[])
{
while(ind<=maxind)
{
fenvik[ind]+=a-b;
ind+=(ind & -ind);
}
}
long long findans(long long ind,long long maxind,long long fenvik[])
{
long long sum=0;
while(ind>0)
{
sum+=fenvik[ind];
ind-=(ind & -ind);
}
return sum;
}
int main()
{
cin>>n>>z;
for(k=1;k<=n;k++)
{
cin>>a[k];
}
for(k=1;k<=n;k++)
{
//pref[k]=pref[k-1]+a[k];
//pref2[k]=pref2[k-1]+a[k]*k;
update(k,n,a[k],0,pref);
update(k,n,a[k]*k,0,pref2);
}
for(k=n;k>=1;k--)
{
//pref3[k]=pref3[k+1]+a[k]*(n-k+1);
update(k,n,a[k]*(n-k+1),0,pref3);
}
int q;
cin>>q;
while(q--)
{
cin>>type;
if(type==2)
{
cin>>l>>r>>m;
long long ans1,ans2,ans3;
if(r-l+1>=m*2)
{
//ans1=pref2[l+m-2]-pref2[l-1];
//ans1-=(pref[l+m-2]-pref[l-1])*(l-1);
ans1=findans(l+m-2,n,pref2)-findans(l-1,n,pref2);
ans1-=(findans(l+m-2,n,pref)-findans(l-1,n,pref))*(l-1);
//ans2=pref3[r-m+2]-pref3[r+1];
//ans2-=(pref[r]-pref[r-m+1])*(n-r);
//ans2=(findans(n,n,pref3)-findans(r-m+1,n,pref3))-(findans(n,n,pref3)-findans(r,n,pref3));
ans2=findans(r,n,pref3)-findans(r-m+1,m,pref3);
ans2-=(findans(r,n,pref)-findans(r-m+1,n,pref))*(n-r);
//ans3=(pref[r-m+1]-pref[l+m-2])*m;
ans3=(findans(r-m+1,n,pref)-findans(l+m-2,n,pref))*m;
cout<<ans1+ans2+ans3<<endl;
}
else
{
if(r-l+1<m)
{
cout<<"0"<<endl;
continue;
}
siz=r-l+1;
cnt=siz-m+1;
//ans1=pref2[l+cnt-2]-pref2[l-1]-(pref[l+cnt-2]-pref[l-1])*(l-1);
ans1=findans(l+cnt-2,n,pref2)-findans(l-1,n,pref2)-(findans(l+cnt-2,n,pref)-findans(l-1,n,pref))*(l-1);
//ans2=pref3[r-cnt+2]-pref3[r+1]-(pref[r]-pref[r-cnt+1])*(n-r);
//ans2=(findans(n,n,pref3)-findans(r-cnt+1,n,pref3))-(findans(n,n,pref3)-findans(r,n,pref3))-(findans(r,n,pref)-findans(r-cnt+1,n,pref))*(n-r);
ans2=findans(r,n,pref3)-findans(r-cnt+1,n,pref3)-(findans(r,n,pref)-findans(r-cnt+1,n,pref))*(n-r);
//ans3=(pref[r-cnt+1]-pref[l+cnt-2])*cnt;
ans3=(findans(r-cnt+1,n,pref)-findans(l+cnt-2,n,pref))*cnt;
cout<<ans1+ans2+ans3<<endl;
}
}
else
{
long long z;
cin>>z;
}
}
}
/*
1 2 3 4
1 3 6 10
1 5 14 30
20 16 10 4
2+6
14 - 1 -(6-1)*(2-1)
1 2 3 4
2 - 4 m = 2
2 3
pref2[(r+l)/2] - pref2[l-1] - (pref[(r+l)/2] - pref[l-1])*(l-1)
8
7 2 5 1 9 3 4 6
3
2 2 6 2
2 5 1 9 3 4
2+10+3
iqamde gaizrdeba sanam l+m!=r
2 3 4 5 6
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
3 ms |
332 KB |
Output is correct |
| 3 |
Correct |
5 ms |
332 KB |
Output is correct |
| 4 |
Correct |
7 ms |
460 KB |
Output is correct |
| 5 |
Correct |
9 ms |
544 KB |
Output is correct |
| 6 |
Correct |
12 ms |
588 KB |
Output is correct |
| 7 |
Correct |
14 ms |
696 KB |
Output is correct |
| 8 |
Correct |
17 ms |
720 KB |
Output is correct |
| 9 |
Correct |
23 ms |
916 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
1212 KB |
Output is correct |
| 2 |
Correct |
75 ms |
2340 KB |
Output is correct |
| 3 |
Correct |
95 ms |
3012 KB |
Output is correct |
| 4 |
Correct |
166 ms |
5156 KB |
Output is correct |
| 5 |
Correct |
242 ms |
7428 KB |
Output is correct |
| 6 |
Correct |
228 ms |
7060 KB |
Output is correct |
| 7 |
Correct |
223 ms |
7116 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
50 ms |
1904 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
