제출 #1268172

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1268172		rayan_bd	Addk (eJOI21_addk)	C++20	0 / 100	85 ms	4228 KiB

Main

// not my code generated by chatgpt

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct segment_tree {
    vector<int> seg;
    int N;
    void init(int n) {
        N = n;
        seg.assign(4 * (n + 5), 0);
    }
    void upd_rec(int node, int start, int end, int idx, int val) {
        if (start == end) {
            seg[node] = val;
            return;
        }
        int mid = start + (end - start) / 2;
        if (idx <= mid) upd_rec(node * 2 + 1, start, mid, idx, val);
        else upd_rec(node * 2 + 2, mid + 1, end, idx, val);
        seg[node] = seg[node * 2 + 1] + seg[node * 2 + 2];
    }
    int query_rec(int node, int start, int end, int l, int r) {
        if (start > r || end < l) return 0;
        if (start >= l && end <= r) return seg[node];
        int mid = start + (end - start) / 2;
        return query_rec(node * 2 + 1, start, mid, l, r) + query_rec(node * 2 + 2, mid + 1, end, l, r);
    }
    // wrappers (1-based indices for array)
    void upd(int pos, int val) { upd_rec(0, 1, N, pos, val); }
    int query(int l, int r) { if (l > r) return 0; return query_rec(0, 1, N, l, r); }
} tr_val, tr_idxmul; // we'll use tr_val for a[i], tr_idxmul for a[i]*i

int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // If you need file IO, you can re-enable these lines:
    // freopen("input.in", "r", stdin);
    // freopen("output.out", "w", stdout);

    int n, k;
    if (!(cin >> n >> k)) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];

    // initialize trees
    tr_val.init(n + 5);
    tr_idxmul.init(n + 5);

    for (int i = 1; i <= n; ++i) {
        tr_val.upd(i, a[i]);
        tr_idxmul.upd(i, a[i] * i);
    }

    int q; cin >> q;
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            // rotate left the k distinct positions
            vector<int> pos(k);
            for (int i = 0; i < k; ++i) cin >> pos[i];
            if (k <= 1) continue; // nothing to do

            int tmp = a[pos[0]];
            for (int i = 0; i + 1 < k; ++i) {
                a[pos[i]] = a[pos[i + 1]];
                tr_val.upd(pos[i], a[pos[i]]);
                tr_idxmul.upd(pos[i], a[pos[i]] * pos[i]);
            }
            a[pos.back()] = tmp;
            tr_val.upd(pos.back(), a[pos.back()]);
            tr_idxmul.upd(pos.back(), a[pos.back()] * pos.back());

        } else {
            int l, r, m; cin >> l >> r >> m;
            int len = r - l + 1;
            if (m > len) { cout << 0 << "\n"; continue; }

            // We split [l,r] into:
            // rising segment: [l, min(r, l + m - 1)] with weight (i - l + 1)
            // middle segment (full weight m): [l + m, r - m + 1] if valid
            // falling segment: [max(l, r - m + 2), r] with weight (r - i + 1)
            int ans = 0;

            // rising:
            int L1 = l;
            int R1 = min(r, l + m - 1);
            if (L1 <= R1) {
                // sum_{i=L1..R1} a[i] * (i - l + 1) = sum a[i]*i - (l-1)*sum a[i]
                int sum_ai_i = tr_idxmul.query(L1, R1);
                int sum_ai = tr_val.query(L1, R1);
                ans += sum_ai_i - (l - 1) * sum_ai;
            }

            // middle plateau where weight = m
            int Lmid = l + m;
            int Rmid = r - m + 1;
            if (Lmid <= Rmid) {
                int sum_ai = tr_val.query(Lmid, Rmid);
                ans += sum_ai * m;
            }

            // falling:
            int L2 = max(l, r - m + 2);
            int R2 = r;
            if (L2 <= R2) {
                // weight = r - i + 1 = (r+1) - i
                // sum a[i]*((r+1)-i) = (r+1)*sum a[i] - sum a[i]*i
                int sum_ai = tr_val.query(L2, R2);
                int sum_ai_i = tr_idxmul.query(L2, R2);
                ans += (r + 1) * sum_ai - sum_ai_i;
            }

            cout << ans << "\n";
        }
    }

    return 0;
}

• Subtask 1: 0 / 36
• Subtask 2: 0 / 56
• Subtask 3: 0 / 8