#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (100005)
ll N,K;
struct fenwick {
ll fw[MAXN], fw2[MAXN];
fenwick() {
memset(fw,0,sizeof(fw));
memset(fw2,0,sizeof(fw2));
}
void update(ll x,ll y,ll v){
y++;
for(ll tx = x;tx <= N;tx += tx&(-tx)) fw[tx] += v,fw2[tx] -= v * (x - 1);
for(ll ty = y;ty <= N;ty += ty&(-ty)) fw[ty] -= v,fw2[ty] += v * (y - 1);
}
long long sum(long long x){
ll ans = 0;
for(ll tx = x;tx;tx -= tx&(-tx)){
ans += (fw[tx] * x) + fw2[tx];
}
return ans;
}
long long range_sum(long long x,long long y){
return sum(y) - sum(x - 1);
}
} front, middle, back;
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);
//note that everything is 1-indexed
cin>>N>>K;
ll arr[N + 1];
for(ll i = 1;i <= N;i++){
cin>>arr[i];
}
arr[0] = 0;
ll pre[N + 1], suf[N + 1];
memset(pre,0,sizeof(pre));
memset(suf,0,sizeof(suf));
for(ll i = 1;i <= N;i++){
pre[i] = arr[i] * i;
}
for(ll i = N;i >= 1;i--){
suf[i] = (arr[i] * (N - i + 1));
}
for(ll i = 1;i <= N;i++){
front.update(i,i,pre[i]);
middle.update(i,i,arr[i]);
back.update(i,i,suf[i]);
}
ll Q;
cin>>Q;
for(ll q = 0;q < Q;q++){
ll t;
cin>>t;
if(t == 1){ //1-indexed
ll index[K];
for(ll i = 0;i < K;i++){
cin>>index[i];
}
for(ll i = 0;i < K - 1;i++){
front.update(index[i],index[i],index[i] * -arr[index[i]] + index[i] * arr[index[i + 1]]);
back.update(index[i],index[i],(N - index[i] + 1) * -arr[index[i]] + (N - index[i] + 1) * arr[index[i + 1]]);
middle.update(index[i],index[i],arr[index[i + 1]] - arr[index[i]]);
}
front.update(index[K - 1],index[K - 1],index[K - 1] * -arr[index[K - 1]] + index[K - 1] * arr[index[0]]);
back.update(index[K - 1],index[K - 1],(N - index[K - 1] + 1) * -arr[index[K - 1]] + (N - index[K - 1] + 1) * arr[index[0]]);
middle.update(index[K - 1],index[K - 1],arr[index[0]] - arr[index[K - 1]]);
ll first = arr[index[0]];
for(ll i = 1;i < K;i++){
arr[index[i - 1]] = arr[index[i]];
pre[index[i - 1]] = index[i - 1] * arr[index[i - 1]];
suf[index[i - 1]] = (N - index[i - 1] + 1) * arr[index[i - 1]];
}
arr[index[K - 1]] = first;
pre[index[K - 1]] = index[K - 1] * arr[index[K - 1]];
suf[index[K - 1]] = (N - index[K - 1] + 1) * arr[index[K - 1]];
}else if(t == 2){ //1-indexed
ll l,r,m;
cin>>l>>r>>m;
ll sum1 = 0, sum2 = 0,sum3 = 0;
if((r - l + 1) - m > 0) sum1 += front.range_sum(l,l + ((r - l + 1) - m) - 1) - (l - 1) * middle.range_sum(l,l + ((r - l + 1) - m) - 1);
if((r - l + 1) - m > 0) sum3 += back.range_sum(r - ((r - l + 1) - m) + 1,r) - (N - r) * middle.range_sum(r - ((r - l + 1) - m) + 1,r);
sum2 += ((r - l + 1) - m + 1) * middle.range_sum(l + ((r - l + 1) - m),r - ((r - l + 1) - m));
cout<<sum1 + sum2 + sum3<<'\n';
}
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
3 ms |
4948 KB |
Output is correct |
| 2 |
Correct |
4 ms |
5032 KB |
Output is correct |
| 3 |
Correct |
3 ms |
5076 KB |
Output is correct |
| 4 |
Correct |
6 ms |
5076 KB |
Output is correct |
| 5 |
Correct |
5 ms |
5204 KB |
Output is correct |
| 6 |
Correct |
5 ms |
5292 KB |
Output is correct |
| 7 |
Correct |
6 ms |
5292 KB |
Output is correct |
| 8 |
Correct |
7 ms |
5332 KB |
Output is correct |
| 9 |
Correct |
8 ms |
5588 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
17 ms |
6228 KB |
Output is correct |
| 2 |
Correct |
23 ms |
6736 KB |
Output is correct |
| 3 |
Correct |
29 ms |
7484 KB |
Output is correct |
| 4 |
Correct |
52 ms |
9356 KB |
Output is correct |
| 5 |
Correct |
93 ms |
11236 KB |
Output is correct |
| 6 |
Correct |
78 ms |
11080 KB |
Output is correct |
| 7 |
Correct |
85 ms |
10996 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
58 ms |
8584 KB |
Output is correct |
| 2 |
Correct |
98 ms |
10472 KB |
Output is correct |
| 3 |
Correct |
201 ms |
12616 KB |
Output is correct |
| 4 |
Correct |
107 ms |
11536 KB |
Output is correct |
