제출 #1280648

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1280648		kkkkk	Addk (eJOI21_addk)	C++20	0 / 100	74 ms	4688 KiB

Main

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

const int N = 1e5 + 11;
const int inf = 1e18;
int a[N], s[N * 4], rs[N * 4], p[N * 4];

void updp(int v, int tl, int tr, int pos, int x){
    if(tl == tr){
        p[v] = x;
        return;
    }
    int mid = (tl + tr) >> 1;
    if(pos <= mid) updp(v + v, tl, mid, pos, x);
    else updp(v + v + 1, mid + 1, tr, pos, x);
    p[v] = p[v + v] + p[v + v + 1];
}

void upds(int v, int tl, int tr, int pos, int x){
    if(tl == tr){
        s[v] = x;
        return;
    }
    int mid = (tl + tr) >> 1;
    if(pos <= mid) upds(v + v, tl, mid, pos, x);
    else upds(v + v + 1, mid + 1, tr, pos, x);
    s[v] = s[v + v] + s[v + v + 1];
}

void updrs(int v, int tl, int tr, int pos, int x){
    if(tl == tr){
        rs[v] = x;
        return;
    }
    int mid = (tl + tr) >> 1;
    if(pos <= mid) updrs(v + v, tl, mid, pos, x);
    else updrs(v + v + 1, mid + 1, tr, pos, x);
    rs[v] = rs[v + v] + rs[v + v + 1];
}

int getp(int v, int tl, int tr, int l, int r){
    if(tl > r || tr < l) return 0;
    if(l <= tl && tr <= r) return p[v];
    int mid = (tl + tr) >> 1;
    return getp(v + v, tl, mid, l, r) + getp(v + v + 1, mid + 1, tr, l, r);
}

int gets(int v, int tl, int tr, int l, int r){
    if(tl > r || tr < l) return 0;
    if(l <= tl && tr <= r) return s[v];
    int mid = (tl + tr) >> 1;
    return gets(v + v, tl, mid, l, r) + gets(v + v + 1, mid + 1, tr, l, r);
}

int getrs(int v, int tl, int tr, int l, int r){
    if(tl > r || tr < l) return 0;
    if(l <= tl && tr <= r) return rs[v];
    int mid = (tl + tr) >> 1;
    return getrs(v + v, tl, mid, l, r) + getrs(v + v + 1, mid + 1, tr, l, r);
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n, k, q;
    cin >> n >> k;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        updp(1, 1, n, i, a[i]);
        upds(1, 1, n, i, a[i] * i);
        updrs(1, 1, n, i, a[i] * (n - i + 1));
    }
    cin >> q;
    while(q--){
        int t;
        cin >> t;
        if(t == 1){
            vector < int > vec;
            deque < int > val;
            for(int i = 0; i < k; i++){
                int x;
                cin >> x;
                vec.push_back(x);
                val.push_back(a[x]);
            }
            // val.push_back(val[0]);
            // val.pop_front();
            // for(int i = 0; i < k; i++){
            //     a[vec[i]] = val[i];
            //     updp(1, 1, n, vec[i], val[i]);
            //     upds(1, 1, n, vec[i], val[i] * vec[i]);
            //     upds(1, 1, n, vec[i], val[i] * (n - vec[i] + 1));
            // }
        }
        else{
            int l, r, m;
            cin >> l >> r >> m;
            cout << getp(1, 1, n, l, r) << ' ';
            int len = (r - l + 1);
            int ans = getp(1, 1, n, l + len - m, r - len + m) * (len - m + 1);
            int L = l, R = l + (len - m) - 1;
            if(L <= R) ans += gets(1, 1, n, L, R) - getp(1, 1, n, L, R) * (L - 1);
            R = r, L = r - (len - m) + 1;
            if(L <= R) ans += getrs(1, 1, n, L, R) - getp(1, 1, n, L, R) * (n - R);
            cout << ans << '\n';
        }
    }
}
// hello karim nurbakyt sanzhar azamat congratulation europa asia america laplas

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