#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 1e6 + 7;
int n, k, q, a[N], old[N];
struct Fenwick {
vector<ll> f;
int n;
Fenwick(int nn) {
n = nn;
f.resize(n + 1);
}
void add(int i, int x) {
for (; i <= n; i += i & -i) f[i] += x;
}
int sum(int i) {
ll res = 0;
for (; i >= 1; i -= i & -i) res += f[i];
return res;
}
int get(int l, int r) {
return sum(r) - sum(l - 1);
}
};
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
}
Fenwick f1(n), f2(n), f3(n);
for (int i = 1; i <= n; ++i) {
f1.add(i, a[i]);
f2.add(i, a[i] * i);
f3.add(i, a[i] * (n - i + 1));
}
cin >> q;
while (q--) {
int t;
cin >> t;
if (t == 1) {
vector<int> v(k);
for (auto &x : v) cin >> x;
for (auto x : v) {
f1.add(x, -a[x]);
f2.add(x, -a[x] * x);
f3.add(x, -a[x] * (n - x + 1));
}
vector<int> rot;
for (int i = 1; i < k; ++i) rot.push_back(v[i]);
rot.push_back(v[0]);
for (int i = 0; i < k; ++i) {
f1.add(v[i], a[rot[i]]);
f2.add(v[i], a[rot[i]] * v[i]);
f3.add(v[i], a[rot[i]] * (n - v[i] + 1));
}
for (int i = 0; i < k; ++i) old[v[i]] = a[v[i]];
for (int i = 0; i < k; ++i) a[v[i]] = old[rot[i]];
} else {
int l, r, m;
cin >> l >> r >> m;
ll ans = 0;
if (r - l + 1 >= 2 * m - 1) {
ans += f2.get(l, l + m - 1) - f1.get(l, l + m - 1) * (l - 1);
ans += f3.get(r - m + 1, r) - f1.get(r - m + 1, r) * (n - r);
if (l + m <= r - m) {
ans += f1.get(l + m, r - m) * m;
}
} else {
int mid = (l + r) / 2;
ans += f2.get(l, mid) - f1.get(l, mid) * (l - 1);
ans += f3.get(mid + 1, r) - f1.get(mid + 1, r) * (n - r);
}
cout << ans << "\n";
}
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
1880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
54 ms |
4632 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
