#include "bits/stdc++.h"
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define int long long
const int NM = 1e6 + 5;
int n, k, q, a[NM], q1[15], tree1[NM<<2], tree2[NM<<2], tree3[NM<<2];
void build1(int *arr, int id = 1, int l = 1, int r = n) {
if (l == r) {
tree1[id] = arr[l];
return;
}
int mid = (l+r) >> 1;
build1(arr, id<<1, l, mid);
build1(arr, id<<1|1, mid+1, r);
tree1[id] = tree1[id<<1] + tree1[id<<1|1];
}
void build2(int *arr, int id = 1, int l = 1, int r = n) {
if (l == r) {
tree2[id] = arr[l] * l;
return;
}
int mid = (l+r) >> 1;
build2(arr, id<<1, l, mid);
build2(arr, id<<1|1, mid+1, r);
tree2[id] = tree2[id<<1] + tree2[id<<1|1];
}
void build3(int *arr, int id = 1, int l = 1, int r = n) {
if (l == r) {
tree3[id] = arr[l] * (n-l+1);
return;
}
int mid = (l+r) >> 1;
build3(arr, id<<1, l, mid);
build3(arr, id<<1|1, mid+1, r);
tree3[id] = tree3[id<<1] + tree3[id<<1|1];
}
void update1(int pos, int val, int id = 1, int l = 1, int r = n) {
if (l == r) {
tree1[id] = val;
return;
}
int mid = (l+r) >> 1;
if (pos <= mid) update1(pos, val, id<<1, l, mid);
else update1(pos, val, id<<1|1, mid+1, r);
tree1[id] = tree1[id<<1] + tree1[id<<1|1];
}
void update2(int pos, int val, int id = 1, int l = 1, int r = n) {
if (l == r) {
tree2[id] = val * l;
return;
}
int mid = (l+r) >> 1;
if (pos <= mid) update2(pos, val, id<<1, l, mid);
else update2(pos, val, id<<1|1, mid+1, r);
tree2[id] = tree2[id<<1] + tree2[id<<1|1];
}
void update3(int pos, int val, int id = 1, int l = 1, int r = n) {
if (l == r) {
tree3[id] = val * (n-l+1);
return;
}
int mid = (l+r) >> 1;
if (pos <= mid) update3(pos, val, id<<1, l, mid);
else update3(pos, val, id<<1|1, mid+1, r);
tree3[id] = tree3[id<<1] + tree3[id<<1|1];
}
int get(int *tree, int u, int v, int id = 1, int l = 1, int r = n) {
if (v < l || r < u) return 0;
if (u <= l && r <= v) return tree[id];
int mid = (l+r) >> 1;
return get(tree, u, v, id<<1, l, mid) + get(tree, u, v, id<<1|1, mid+1, r);
}
int get_sum1(int l, int r) {
if (l > r) return 0;
return get(tree1, l, r);
}
int get_sum2(int l, int r) {
if (l > r) return 0;
return get(tree2, l, r) - get_sum1(l, r) * (l-1);
}
int get_sum3(int l, int r) {
if (l > r) return 0;
return get(tree3, l, r) - get_sum1(l, r) * (n-r);
}
signed main() {
IOS;
cin >> n >> k;
for (int i = 1; i <= n; ++i) cin >> a[i];
build1(a);
build2(a);
build3(a);
cin >> q;
while (q--) {
int type;
cin >> type;
if (type == 1) {
for (int i = 1; i <= k; ++i) cin >> q1[i];
for (int i = 2; i <= k; ++i) swap(a[q1[i]], a[q1[i-1]]);
for (int i = 1; i <= k; ++i) {
update1(q1[i], a[q1[i]]);
update2(q1[i], a[q1[i]]);
update3(q1[i], a[q1[i]]);
}
continue;
}
int l, r, m;
cin >> l >> r >> m;
if (r-l+1 < m) {
cout << "0\n";
continue;
}
int u, v, d = min(r-l+1-m, m-1);
u = l+d;
v = r-d;
cout << get_sum2(l, u-1) + get_sum1(u, v) * (d+1) + get_sum3(v+1, r) << "\n";
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
336 KB |
Output is correct |
| 3 |
Correct |
3 ms |
476 KB |
Output is correct |
| 4 |
Correct |
4 ms |
596 KB |
Output is correct |
| 5 |
Correct |
6 ms |
596 KB |
Output is correct |
| 6 |
Correct |
6 ms |
820 KB |
Output is correct |
| 7 |
Correct |
8 ms |
820 KB |
Output is correct |
| 8 |
Correct |
11 ms |
852 KB |
Output is correct |
| 9 |
Correct |
14 ms |
1236 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
29 ms |
2244 KB |
Output is correct |
| 2 |
Correct |
43 ms |
2456 KB |
Output is correct |
| 3 |
Correct |
60 ms |
4300 KB |
Output is correct |
| 4 |
Correct |
119 ms |
7988 KB |
Output is correct |
| 5 |
Correct |
177 ms |
8780 KB |
Output is correct |
| 6 |
Correct |
151 ms |
8544 KB |
Output is correct |
| 7 |
Correct |
158 ms |
8520 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
121 ms |
4308 KB |
Output is correct |
| 2 |
Correct |
211 ms |
8184 KB |
Output is correct |
| 3 |
Correct |
296 ms |
7980 KB |
Output is correct |
| 4 |
Correct |
190 ms |
8688 KB |
Output is correct |
