Submission #1259349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1259349		minhpk	Addk (eJOI21_addk)	C++20	100 / 100	609 ms	11604 KiB

Main

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

int a, b;
int z[1000005];
vector<long long> bit;

void bit_init(int n) {
    bit.assign(n+1, 0);
}

void bit_update(int i, long long v) {
    for (; i <= a; i += i & -i) bit[i] += v;
}

long long bit_query(int i) {
    long long s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

struct node {
    int l, r;
    long long val, val1;
};

node f[4000005];

node combine(const node &A, const node &B) {
    if (A.l == 0) return B;
    if (B.r == 0) return A;
    node res;
    res.l = A.l;
    res.r = B.r;
    long long sumB = bit_query(B.r) - bit_query(B.l - 1);
    long long sumA = bit_query(A.r) - bit_query(A.l - 1);
    res.val  = A.val  + B.val  + sumB * (A.r - A.l + 1);
    res.val1 = A.val1 + B.val1 + sumA * (B.r - B.l + 1);
    return res;
}

void build(int id, int l, int r) {
    if (l == r) {
        f[id].l = l;
        f[id].r = l;
        f[id].val  = z[l];
        f[id].val1 = z[l];
        return;
    }
    int mid = (l + r) / 2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    f[id] = combine(f[id*2], f[id*2+1]);
}

void update(int id,int l,int r,int pos,int val){
    if (l==r){
         f[id].val=f[id].val1=val;
         return;
    }
    int mid=(l+r)/2;
    if (pos<=mid){
        update(id*2,l,mid,pos,val);
    }else{
        update(id*2+1,mid+1,r,pos,val);
    }
    f[id]=combine(f[id*2],f[id*2+1]);
}
node get(int id, int l, int r, int x, int y) {
    if (x > r || y < l) return {0, 0, 0, 0};
    if (l >= x && r <= y) return f[id];
    int mid = (l + r) / 2;
    return combine(
        get(id*2, l, mid, x, y),
        get(id*2+1, mid+1, r, x, y)
    );
}

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

    cin >> a >> b;
    bit_init(a);
    for (int i = 1; i <= a; i++) {
        cin >> z[i];
        bit_update(i, z[i]);
    }
    build(1, 1, a);

    int q;
    cin >> q;
    while (q--) {
        int c;
        cin >> c;
        if (c == 1) {
            vector<int> idx(b);
            for (int i = 0; i < b; i++) cin >> idx[i];
            vector<int> v;
            for (int i=1;i<b;i++){
                 v.push_back(z[idx[i]]);
            }
            v.push_back(z[idx[0]]);
            for (int i=0;i<b;i++){
                 bit_update(idx[i],-z[idx[i]]);
                 z[idx[i]]=v[i];
                 bit_update(idx[i],z[idx[i]]);
                 update(1,1,a,idx[i],z[idx[i]]);
            }
        } else {
            int l, r, t;
            cin >> l >> r >> t;
            int p = min(t, (r - l + 1) - t + 1);
            long long res = 0;
            res += get(1, 1, a, l, l + p - 1).val;
            res += get(1, 1, a, r - p + 1, r).val1;
            long long midSum = bit_query(r - p) - bit_query(l + p - 1);
            res += midSum * p;
            cout << res << '\n';
        }
    }
    return 0;
}

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