Submission #1209819

#TimeUsernameProblemLanguageResultExecution timeMemory
1209819sunflowerAddk (eJOI21_addk)C++17
92 / 100
91 ms7804 KiB
#include <bits/stdc++.h> using namespace std; int n, numPerm, q; #define MAX_N 100'100 int a[MAX_N + 2]; int id[12]; long long pre[MAX_N + 2], sum[MAX_N + 2]; struct node { long long pre, sum; node operator + (const node &other) const { return {pre + other.pre, sum + other.sum}; } }; struct Segtree { node seg[4 * MAX_N + 7]; void build(int id, int l, int r) { if (l == r) { seg[id].pre = a[l]; seg[id].sum = 1LL * a[l] * l; return; } int g = (l + r) >> 1; build(id << 1, l, g); build(id << 1 | 1, g + 1, r); seg[id] = seg[id << 1] + seg[id << 1 | 1]; } void update(int id, int l, int r, int pos, int val) { while (l < r) { int g = (l + r) >> 1; if (pos <= g) { id = 2 * id; r = g; } else { id = 2 * id + 1; l = g + 1; } } seg[id].pre = val; seg[id].sum = 1LL * pos * val; while (id > 1) { id >>= 1; seg[id] = seg[id << 1] + seg[id << 1 | 1]; } } node get(int id, int l, int r, int u, int v) { if (l > v || u > r) return {0, 0}; if (u <= l && r <= v) return seg[id]; int g = (l + r) >> 1; return get(id << 1, l, g, u, v) + get(id << 1 | 1, g + 1, r, u, v); } void update(int pos, int val) { update(1, 1, n, pos, val); } node get(int l, int r) { return get(1, 1, n, l, r); } } st; #undef MAX_N int main() { ios_base::sync_with_stdio(false);cin.tie(nullptr); // freopen("test.inp","r",stdin); // freopen("test.out","w",stdout); cin >> n >> numPerm; pre[0] = sum[0] = 0; for (int i = 1; i <= n; ++i) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; sum[i] = sum[i - 1] + 1LL * a[i] * i; } st.build(1, 1, n); cin >> q; while (q--) { int type; cin >> type; if (type == 1) { for (int i = 1; i <= numPerm; ++i) cin >> id[i]; if (numPerm == 1) continue; int tmp = a[id[1]]; for (int i = 1; i < numPerm; ++i) { a[id[i]] = a[id[i + 1]]; st.update(id[i], a[id[i]]); } a[id[numPerm]] = id[1]; st.update(id[numPerm], a[id[numPerm]]); } else { int L, R, range; cin >> L >> R >> range; if (R - L + 1 < range) {cout << "0\n"; continue;} int num = (R - L + 1) - range + 1; range = min(range, num); long long ans = 0; int pref = L + range - 2; node T1 = st.get(L, pref); // ans += sum[pref] - sum[L - 1] - 1LL * (L - 1) * (pre[pref] - pre[L - 1]); ans += T1.sum - 1LL * (L - 1) * T1.pre; L = pref + 1; int rig = max(pref + 1, R - range + 2); if (rig <= R) { node T2 = st.get(rig, R); ans += 1LL * (R + 1) * T2.pre - T2.sum; } R = rig - 1; if (L <= R) { node T3 = st.get(L, R); ans += 1LL * range * T3.pre; } cout << ans << "\n"; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...