#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll=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*2, l, mid);
build1(arr, id*2+1, mid+1, r);
tree1[id] = tree1[id*2] + tree1[id*2+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*2, l, mid);
build2(arr, id*2+1, mid+1, r);
tree2[id] = tree2[id*2] + tree2[id*2+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*2, l, mid);
build3(arr, id*2+1, mid+1, r);
tree3[id] = tree3[id*2] + tree3[id*2+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*2] + tree1[id*2+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*2] + tree2[id*2+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*2] + tree3[id*2+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);
}
main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
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";
}
}
Compilation message
worst_reporter3.cpp:88:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
88 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
104 ms |
58316 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
98 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
104 ms |
58316 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
