#include<bits/stdc++.h>
using namespace std;
struct node{
int sumR,sum,sumL,size;
};
node t[400001];
node merge(node a,node b){
node res;
res.sum=a.sum+b.sum;
res.sumL=a.sumL+b.sumL+b.sum*a.size;
res.sumR=b.sumR+a.sumR+a.sum*b.size;
res.size=a.size+b.size;
return res;
}
node new_val(int a){
node res;
res.sum=res.sumR=res.sumL=a;
res.size=1;
if (a==-1){
res.sum=res.sumR=res.sumL=0;
res.size=0;
}
return res;
}
void update(int v,int tl,int tr,int ind,int val){
if (tl==tr)t[v]=new_val(val);else{
int tm=(tl+tr)/2;
if (ind<=tm)update(v*2,tl,tm,ind,val);else update(v*2+1,tm+1,tr,ind,val);
t[v]=merge(t[v*2],t[v*2+1]);
}
}
node query(int v,int tl,int tr,int l,int r){
if (l>r)return new_val(-1);
if (l==tl && r==tr)return t[v];
int tm=(tl+tr)/2;
return merge(query(v*2,tl,tm,l,min(r,tm)),query(v*2+1,tm+1,tr,max(l,tm+1),r));
}
int main(){
int n,k;
cin>>n>>k;
int a[n+1];
for (int i=1;i<=n;i++){
cin>>a[i];
update(1,1,n,i,a[i]);
}
int q;
cin>>q;
while (q--){
int t;
cin>>t;
if (t==1){
vector <int> v;
v.push_back(0);
int x[k+1];
for (int i=1;i<=k;i++){
cin>>x[i];
if (i!=1)v.push_back(x[i]);
}
v.push_back(x[1]);
for (int i=1;i<=k;i++){
a[x[i]]=a[v[i]];
update(1,1,n,x[i],a[x[i]]);
}
}else{
int l,r,m;
cin>>l>>r>>m;
if (r-l+1>=2*m-2){
cout<<query(1,1,n,l,l+m-2).sumL+query(1,1,n, r-m+2,r).sumR+query(1,1,n,l+m-1,r-m+1).sum*m<<"\n";
}else{
cout<<query(1,1,n,l,l+m-2).sumL+query(1,1,n, r-m+2,r).sumR-query(1,1,n,r-m+2,l+m-2).sum*(n-1)<<"\n";
}
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
308 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
73 ms |
2068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
237 ms |
4752 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
