#include<bits/stdc++.h>
using namespace std;
int n,k,a[100009],pref[200009],pref2[200009],pref3[2000009],type,l,r,m,siz,z,cnt,new_n=1,fans;
int get(int a[],int l,int r,int L,int R,int ind)
{
int x=0;
if(l>r) return x;
if(r<L || l>R) return x;
if(l>=L && r<=R) return a[ind];
return get(a,l,(l+r)/2,L,R,ind*2)+get(a,(l+r)/2+1,r,L,R,ind*2+1);
}
void update(int a[],int ind)
{
a[ind]=a[ind*2]+a[ind*2+1];
if(ind!=1) update(a,ind/2);
}
int main()
{
cin>>n>>z;
for(k=1;k<=n;k++)
{
cin>>a[k];
}
while(new_n<n)
{
new_n*=2;
}
for(k=new_n;k<=new_n+n-1;k++)
{
pref[k]=a[k-new_n+1];
pref2[k]=a[k-new_n+1]*(k-new_n+1);
pref3[k]=a[k-new_n+1]*((new_n+n)-k);
}
for(k=new_n-1;k>=1;k--)
{
pref[k]=pref[k*2]+pref[k*2+1];
pref2[k]=pref2[k*2]+pref2[k*2+1];
pref3[k]=pref3[k*2]+pref3[k*2+1];
}
//cout<<get(pref,1,new_n,1,1,1);
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=get(pref2,1,new_n,l,l+m-2,1);
ans1-=get(pref,1,new_n,l,l+m-2,1)*(l-1);
ans2=get(pref3,1,new_n,r-m+2,r,1);
ans2-=get(pref,1,new_n,r-m+2,r,1)*(n-r);
ans3=get(pref,1,new_n,l+m-1,r-m+1,1)*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=get(pref2,1,new_n,l,l+cnt-2,1)-get(pref,1,new_n,l,l+cnt-2,1)*(l-1);
//ans1=pref2[l+cnt-2]-pref2[l-1]-(pref[l+cnt-2]-pref[l-1])*(l-1);
ans2=get(pref3,1,new_n,r-cnt+2,r,1)-get(pref,1,new_n,r-cnt+2,r,1)*(n-r);
//ans2=pref3[r-cnt+2]-pref3[r+1]-(pref[r]-pref[r-cnt+1])*(n-r);
ans3=get(pref,1,new_n,l+cnt-1,r-cnt+1,1)*cnt;
//ans3=(pref[r-cnt+1]-pref[l+cnt-2])*cnt;
cout<<ans1+ans2+ans3<<endl;
}
}
else
{
int x;
vector<long long> v1,v2;
for(int i=1;i<=z;i++)
{
cin>>x;
v1.push_back(x);
v2.push_back(a[x]);
}
for(int i=0;i<z-1;i++)
{
a[v1[i]]=v2[i+1];
pref[v1[i]+new_n-1]=v2[i+1];
pref2[v1[i]+new_n-1]=v2[i+1]*v1[i];
pref3[v1[i]+new_n-1]=v2[i+1]*(n-v1[i]+1);
}
a[v1[z-1]]=v2[0];
pref[v1[z-1]+new_n-1]=v2[0];
pref2[v1[z-1]+new_n-1]=v2[0]*v1[z-1];
pref3[v1[z-1]+new_n-1]=v2[0]*(n-v1[z-1]+1);
for(int i=0;i<v1.size();i++)
{
update(pref,(v1[i]+new_n-1)/2);
update(pref2,(v1[i]+new_n-1)/2);
update(pref3,(v1[i]+new_n-1)/2);
}
}
}
}
/*
7 9 5 1 6 3 4 2
9 + 10 + 4 + 6 = 29
21
*/
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:105:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
105 | for(int i=0;i<v1.size();i++)
| ~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
4 ms |
332 KB |
Output is correct |
| 3 |
Incorrect |
8 ms |
436 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
94 ms |
1624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
245 ms |
4144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
