#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define sz size()
using namespace std;
[[maybe_unused]]const int e6=1e6;
[[maybe_unused]]const int e7=1e7;
[[maybe_unused]]const int e8=1e8;
[[maybe_unused]]const int e9=1e9;
inline int rd(){
int num;cin>>num;
return num;
}
inline ll rdll(){
ll num;cin>>num;
return num;
}
[[maybe_unused]]const ll inf=1e18+7;
[[maybe_unused]]const ll MOD=1e9+7;
[[maybe_unused]]const int N=1e6+3;
struct trio{
ll res,sum;
int cnt;
};
trio t_l[N],t_r[N];
trio merge_r(trio A,trio B){
trio C={0,0,0};
C.res=A.res+B.res+(ll)A.cnt*B.sum;
C.sum=A.sum+B.sum;
C.cnt=A.cnt+B.cnt;
return C;
}
trio merge_l(trio A,trio B){
trio C={0,0,0};
C.res=A.res+B.res+(ll)B.cnt*A.sum;
C.sum=A.sum+B.sum;
C.cnt=A.cnt+B.cnt;
return C;
}
int n;
void upd(int pos,int x,int v=1,int tl=1,int tr=n){
if(tl==tr){
t_l[v]={x,x,1};
t_r[v]={x,x,1};
return;
}
int md=(tl+tr)>>1;
if(pos<=md)upd(pos,x,v+v,tl,md);
else upd(pos,x,v+v+1,md+1,tr);
t_l[v]=merge_l(t_l[v+v],t_l[v+v+1]);
t_r[v]=merge_r(t_r[v+v],t_r[v+v+1]);
}
trio get_r(int l,int r,int v=1,int tl=1,int tr=n){
if(tl>=l&&tr<=r)return t_r[v];
if(tl>r||l>tr)return {0,0,0};
int md=(tl+tr)>>1;
return merge_r(get_r(l,r,v+v,tl,md),get_r(l,r,v+v+1,md+1,tr));
}
trio get_l(int l,int r,int v=1,int tl=1,int tr=n){
if(tl>=l&&tr<=r)return t_l[v];
if(tl>r||l>tr)return {0,0,0};
int md=(tl+tr)>>1;
return merge_l(get_l(l,r,v+v,tl,md),get_l(l,r,v+v+1,md+1,tr));
}
// max(l,i-m+1)
// min(r-m+1,i) - max(l,i-m+1)
int get(int i,int l,int r,int m){
return min(r-m+1,i)-max(l,i-m+1)+1;
}
int a[N],b[N];
int vals[N];
int find(int lq,int rq,int L,int R,int m,int x){
int l=lq,r=rq,res=lq;
while(r>=l){
int md=(r+l)>>1;
if(get(md,L,R,m)==x){
res=md;
l=md+1;
}
else r=md-1;
}
return res;
}
void code(){
int k;cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>vals[i];
upd(i,vals[i]);
}
int q;cin>>q;
while(q--){
int tp;cin>>tp;
if(tp==1){
for(int i=0;i<k;i++)cin>>a[i];
for(int i=0;i<k;i++)b[i]=vals[a[(i+1)%k]];
for(int i=0;i<k;i++){
vals[a[i]]=b[i];
upd(a[i],vals[a[i]]);
}
continue;
}
int l,r,m;cin>>l>>r>>m;
int md=(l+r)>>1;
int x=get(md,l,r,m);
int R=find(md,r,l,r,m,x);
int L=l+(r-R);
ll res=get_r(L,R).sum*(ll)x;
if(l!=L)res+=get_r(l,L-1).res;
if(r!=R)res+=get_l(R+1,r).res;
cout<<res<<"\n";
}
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
int tt=1;
// cin>>tt;
while(tt--)code(),cout<<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |