Submission #912528

#	Time	Username	Problem	Language	Result	Execution time	Memory
912528		andro	Addk (eJOI21_addk)	C++14	100 / 100	442 ms	22012 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
 
int arr[100001];
 
struct node {
    int s, e, m, val, incre, decre;
    node *l, *r;
    node(int S, int E) {
        s = S;
        e = E;
        m = (s + e) / 2;
        val = 0; incre = 0; decre = 0;
        if (s != e) {
            l = new node(s, m);
            r = new node(m + 1, e);
        }
    }
    void update(int X, int V) {
        if (s == e) {
            val = V;
            incre = V;
            decre = V;
        } else {
            if (X <= m) {
                l -> update(X, V);
            } else {
                r -> update(X, V);
            }
            val = l -> val + r -> val;
            incre = l -> incre + ((r -> s - l -> s) * r -> val) + r -> incre;
            decre = r -> decre + ((r -> e - l -> e) * l -> val) + l -> decre;
        }
    }
    int query(int S, int E) {
        if (S > E) {
            return 0;
        }
        if (s == S && e == E) {
            return val;
        } else {
            if (E <= m) {
                return l -> query(S, E);
            } else if (S > m) {
                return r -> query(S, E);
            } else {
                return l -> query(S, m) + r -> query(m + 1, E);
            }
        }
    }
    int query2(int S, int E, int left) {
        if (S > E) {
            return 0;
        }
        if (s == S && e == E) {
            return val * (s - left) + incre;
        } else {
            if (E <= m) {
                return l -> query2(S, E, left);
            } else if (S > m) {
                return r -> query2(S, E, left);
            } else {
                return l -> query2(S, m, left) + r -> query2(m + 1, E, left);
            }
        }
    }
    int query3(int S, int E, int right) {
        if (S > E) {
            return 0;
        }
        if (s == S && e == E) {
            return val * (right - e) + decre;
        } else {
            if (E <= m) {
                return l -> query3(S, E, right);
            } else if (S > m) {
                return r -> query3(S, E, right);
            } else {
                return l -> query3(S, m, right) + r -> query3(m + 1, E, right);
            }
        }
    }
} *root;
 
int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n, k;
    cin >> n >> k;
    root = new node(1, n);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        root -> update(i, arr[i]);
    }
    int q;
    cin >> q;
    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            vector<int> v;
            vector<int> value;
            for (int i = 0; i < k; i++) {
                int a;
                cin >> a;
                v.push_back(a);
                value.push_back(arr[a]);
            }
            root -> update(v[k - 1], arr[v[0]]);
            for (int i = 0; i < k - 1; i++) {
                root -> update(v[i], arr[v[i + 1]]);
            }
            arr[v[k - 1]] = value[0];
            for (int i = 0; i < k - 1; i++) {
                arr[v[i]] = value[i + 1];
            }
        } else {
            int l, r, m;
            cin >> l >> r >> m;
            if (m > (r - l) / 2 + 1) {
                m = r - l + 2 - m;
            }
            int ans = (root -> query(l + m - 1, r - m + 1)) * m;
            ans += root -> query2(l, l + m - 2, l);
            ans += root -> query3(r - m + 2, r, r);
            cout << ans << '\n';
        }
    }
}

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