제출 #530790

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
530790		fabijan_cikac	Addk (eJOI21_addk)	C++17	0 / 100	108 ms	2792 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define ll long long int
#define F first
#define S second
#define pl pair<ll, ll>

const int N = (1 << 21);

int n, k, q;
ll a[N]; pl t[4 * N];

void update(int x, int l, int r, ll val){
    if (x == 0 || l > r) return;
    if (l == r)
        t[x] = {val, val};
    else{
        int mid = (l + r) / 2; t[x] = {t[2 * x].F + t[2 * x + 1].F, t[2 * x].S + t[2 * x + 1].S + (mid - l + 1) * t[2 * x + 1].F};
    }
    if (x & 1)
        update(x / 2, l - (r - l + 1), r, val);
    else update(x / 2, l, r + (r - l + 1), val);
}

//t[x].F - suma uzastopnih, t[x].S - suma ljestvicnih
pl query(int x, int l, int r, int ql, int qr){
    if (ql > r || qr < l || ql > qr)
        return {0, 0};
    if (ql >= l && qr <= r)
        return t[x];
    int mid = (ql + qr) / 2;
    pl val1 = query(2 * x, l, r, ql, mid);
    pl val2 = query(2 * x + 1, l, r, mid + 1, qr);
    if (val1.F == 0)
        return t[x] = val2;
    else if (val2.F == 0)
        return t[x] = val1;
    return t[x] = {val1.F + val2.F, val1.S + val2.S + (ll)(mid - ql) * val2.F};
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> k;
    for (int i = 0; i < n; ++i){
        cin >> a[i]; update(N + i, i + 1, i + 1, a[i]);
    }
    cin >> q;
    for (int i = 0; i < q; ++i){
        int u; cin >> u;
        if (u == 1){
            vector<ll> v; v.resize(k);
            for (int j = 0; j < k; ++j){
                cin >> v[j]; --v[j];
            }
            ll val = a[v[0]];
            for (int j = 0; j < k - 1; ++j)
                a[v[j]] = a[v[j + 1]];
            a[v[k - 1]] = val;
            for (int j = 0; j < k; ++j)
                update(N + v[j], v[j] + 1, v[j] + 1, a[v[j]]);
        }
        else{
            int l, r, m; cin >> l >> r >> m; ll val; int x, y;
            if ((r - l + 1) >= 2 * m){
                val = m - 1; x = l + m - 1; y = r - (m - 1);
            }
            else if (m == r - l + 1){
                val = 0; x = l; y = r;
            }
            else{
                val = (r - l + 1) / 2;
                if ((r - l + 1) % 2 == 0)
                    --val;
                x = l + val; y = r - val;
            }
            ll sum = (val + 1) * query(1, y + 1, r, 1, N).F - query(1, y + 1, r, 1, N).S;
            ll sum1 = query(1, l, x - 1, 1, N).S; ll sum2 = (val + 1) * query(1, x, y, 1, N).F;
            cout << sum + sum1 + sum2 << '\n';
        }
    }

    return 0;
}

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