제출 #1285346

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1285346		okahak71	Addk (eJOI21_addk)	C++20	100 / 100	185 ms	6800 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define ss second
#define ff first
using namespace std;
#pragma GCC optimize("O3")

const ll N = 1e5 + 5;
pair<ll, ll> st[4 * N];
vector<ll>a;

void build(ll l, ll r, ll v){
    if(l == r){
        st[v] = {a[l], a[l] * (l + 1)};
        return ;
    }
    ll mid = (l + r) >> 1;
    build(l, mid, (v << 1)); build(mid + 1, r, (v << 1) + 1);
    st[v] = {st[(v << 1)].ff + st[(v << 1) + 1].ff, st[(v << 1)].ss + st[(v << 1) + 1].ss};
}

pair<ll, ll> get(ll l, ll r, ll ql, ll qr, ll v){
    if(r < ql or l > qr) return {0, 0};
    if(ql <= l and qr >= r) return st[v];
    ll mid = (l + r) >> 1;
    pair<ll, ll> p1 = get(l, mid, ql, qr, (v << 1));
    pair<ll, ll> p2 = get(mid + 1, r, ql, qr, (v << 1) + 1);
    return {p1.ff + p2.ff, p1.ss + p2.ss};
}

void upd(ll l, ll r, ll id, ll val, ll v){
    if(l == r){
        a[l] = val;
        st[v] = {a[l], a[l] * (l + 1)};
        return ;
    }
    ll mid = (l + r) >> 1;
    if(id <= mid) upd(l, mid, id, val, (v << 1));
    else upd(mid + 1, r, id, val, (v << 1) + 1);
    st[v] = {st[(v << 1)].ff + st[(v << 1) + 1].ff, st[(v << 1)].ss + st[(v << 1) + 1].ss};
}

void _(){
    ll n, kk; cin >> n >> kk;
    a.resize(n); for(ll &i : a) cin >> i;
    ll q; cin >> q; build(0, n - 1, 1);
    while(q--){
        ll t; cin >> t;
        if(t == 1){
            vector<ll>ids(kk + 1);
            for(ll i = 0; i < kk; i++) {cin >> ids[i]; --ids[i];}
            if(!kk) continue ;
            ids[kk] = ids[0]; ll st = a[ids[0]];
            for(ll i = 1; i <= kk; i++){
                upd(0, n - 1, ids[i - 1], a[ids[i]], 1);
            } upd(0, n - 1, ids[kk - 1], st, 1);
        }
        else{
            ll l, r, m; cin >> l >> r >> m;
            ll sz = r - l + 1, p1, mid, p2, k = min(m, sz - m + 1);
            auto pr1 = get(0, n - 1, 0, r - k, 1);
            auto pr2 = get(0, n - 1, 0, l + k - 3, 1);
            auto pr3 = get(0, n - 1, 0, l - 2, 1);
            auto pr4 = get(0, n - 1, 0, r - 1, 1);
            mid = k * (pr1.ff - pr2.ff);
            p1 = (pr2.ss - pr3.ss) - (pr2.ff - pr3.ff) * (l - 1); 
            p2 = (pr4.ff - pr1.ff) * k - ((pr4.ss - pr1.ss) - (pr4.ff - pr1.ff) * (r - k + 1));
            cout << p1 + mid + p2 << '\n';
        }
    }
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0); _();
}

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