#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,shes[100];
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
{
if(z==1) continue;
for(int i=1;i<=z;i++)
{
cin>>shes[i];
}
for(int i=1;i<=z-1;i++)
{
update(shes[i],n,a[shes[i+1]],a[shes[i]],pref);
update(shes[i],n,a[shes[i+1]]*shes[i],a[shes[i]]*shes[i],pref2);
update(shes[i],n,a[shes[i+1]]*(n-shes[i]+1),a[shes[i]]*(n-shes[i]+1),pref3);
}
update(shes[z],n,a[shes[0]],a[shes[z]],pref);
update(shes[z],n,a[shes[0]]*shes[z],a[shes[z]]*shes[z],pref2);
update(shes[z],n,a[shes[0]]*(n-shes[z]+1),a[shes[z]]*(n-shes[z]+1),pref3);
long long o=a[shes[1]];
for(int i=1;i<=z-1;i++)
{
shes[i]=shes[i+1];
}
shes[z]=o;
}
}
}
/*
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 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
47 ms |
1108 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
150 ms |
2332 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
