#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef long double ld;
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,1:0;}
template <typename T> bool chkmax(T &x,T y){return x<y?x=y,1:0;}
ll readint(){
ll x=0,f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,k,q;
int a[100005],b[100005],ids[15];
ll sum[800005][3];
void build(int id,int l,int r){
if(l==r){
sum[id][0]=a[l];
sum[id][1]=a[l]*1ll*l;
sum[id][2]=a[l]*1ll*(n-l+1);
return;
}
int mid=(l+r)/2;
build(id<<1,l,mid);
build(id<<1|1,mid+1,r);
sum[id][0]=sum[id<<1][0]+sum[id<<1|1][0];
sum[id][1]=sum[id<<1][1]+sum[id<<1|1][1];
sum[id][2]=sum[id<<1][2]+sum[id<<1|1][2];
}
ll query(int id,int l,int r,int ql,int qr,int t){
if(ql<=l&&r<=qr) return sum[id][t];
int mid=(l+r)/2;
if(qr<=mid) return query(id<<1,l,mid,ql,qr,t);
else if(ql>mid) return query(id<<1|1,mid+1,r,ql,qr,t);
else return query(id<<1,l,mid,ql,qr,t)+query(id<<1|1,mid+1,r,ql,qr,t);
}
void change(int id,int l,int r,int p){
if(l==r){
sum[id][0]=a[l];
sum[id][1]=a[l]*1ll*l;
sum[id][2]=a[l]*1ll*(n-l+1);
return;
}
int mid=(l+r)/2;
if(p<=mid) change(id<<1,l,mid,p);
else change(id<<1|1,mid+1,r,p);
sum[id][0]=sum[id<<1][0]+sum[id<<1|1][0];
sum[id][1]=sum[id<<1][1]+sum[id<<1|1][1];
sum[id][2]=sum[id<<1][2]+sum[id<<1|1][2];
}
int main(){
n=readint(); k=readint();
for(int i=1;i<=n;i++) a[i]=readint();
build(1,1,n);
q=readint();
while(q--){
int op=readint();
if(op==1){
for(int i=1;i<=k;i++) ids[i]=readint();
for(int i=1;i<=k;i++) b[ids[i]]=a[ids[i]];
for(int i=1;i<=k;i++){
a[ids[i]]=b[ids[(i%k)+1]];
change(1,1,n,ids[i]);
}
}else{
int l=readint(),r=readint(),m=readint();
ll res=0;
int low=l,high=r-m+1,p=l;
while(low<=high){
int mid=(low+high)/2;
if(min({mid-l+1,m})==mid-l+1) p=mid,low=mid+1;
else high=mid-1;
}
res+=query(1,1,n,l,p,1)-query(1,1,n,l,p,0)*(l-1);
low=p+1,high=r;
int q=-1;
while(low<=high){
int mid=(low+high)/2;
if(min({r-mid+1,m,min(mid,r-m+1)-l+1})==r-mid+1) q=mid,high=mid-1;
else low=mid+1;
}
if(p<q) res+=query(1,1,n,q,r,2)-query(1,1,n,q,r,0)*(n-r);
if(p+1<q) res+=query(1,1,n,p+1,q-1,0)*min(m,(r-l+1)-m+1);
printf("%lld\n",res);
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
452 KB |
Output is correct |
| 3 |
Correct |
2 ms |
604 KB |
Output is correct |
| 4 |
Correct |
4 ms |
2652 KB |
Output is correct |
| 5 |
Correct |
4 ms |
2652 KB |
Output is correct |
| 6 |
Correct |
6 ms |
2652 KB |
Output is correct |
| 7 |
Correct |
8 ms |
2908 KB |
Output is correct |
| 8 |
Correct |
8 ms |
2904 KB |
Output is correct |
| 9 |
Correct |
12 ms |
2908 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
3416 KB |
Output is correct |
| 2 |
Correct |
45 ms |
3884 KB |
Output is correct |
| 3 |
Correct |
49 ms |
6412 KB |
Output is correct |
| 4 |
Correct |
111 ms |
10068 KB |
Output is correct |
| 5 |
Correct |
134 ms |
11348 KB |
Output is correct |
| 6 |
Correct |
129 ms |
11084 KB |
Output is correct |
| 7 |
Correct |
138 ms |
11016 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
6852 KB |
Output is correct |
| 2 |
Correct |
130 ms |
10728 KB |
Output is correct |
| 3 |
Correct |
159 ms |
12624 KB |
Output is correct |
| 4 |
Correct |
181 ms |
11744 KB |
Output is correct |
