小萌新模板求卡常
查看原帖
小萌新模板求卡常
378467
Windy_YY楼主2024/9/27 09:21
#include <bits/stdc++.h>

using namespace std;

const int N = (int) 2e6 + 233;
int n, m, a[N];
struct Node {
    int l, r, i, key, size, value, sum, lazy;
} z[N];
int root, idx;
int gn(int i, int v) {
    z[++ idx] = {0, 0, i, rand(), 1, v, v, 0};
    return idx;
}
void pushup(int &p) {
    z[p].size = z[z[p].l].size + z[z[p].r].size + 1;
    z[p].sum = z[z[p].l].sum + z[z[p].r].sum + z[p].value;
    z[p].lazy = 0;
}
void rightMove(int &p) {
    int q = z[p].l;
    z[p].l = z[q].r;
    z[q].r = p;
    p = q;
    pushup(z[p].r);
    pushup(p);
}
void leftMove(int &p) {
    int q = z[p].r;
    z[p].r = z[q].l;
    z[q].l = p;
    p = q;
    pushup(z[p].l);
    pushup(p);
}
void insert(int &p, int i, int v) {
    if (!p)
        p = gn(i, v);
    else if (i < z[p].i) {
        insert(z[p].l, i, v);
        if (z[z[p].l].key > z[p].key)
            rightMove(p);
    } else {
        insert(z[p].r, i, v);
        if (z[z[p].r].key > z[p].key)
            leftMove(p);
    } pushup(p);
}
void color(int p, int v) {
    z[p].sum += z[p].size * v;
    z[p].lazy += v;
}
void pushdown(int p) {
    if (z[p].lazy) {
        color(z[p].l, z[p].lazy);
        color(z[p].r, z[p].lazy);
        z[p].value += z[p].lazy;
        z[p].lazy = 0;
    }
}
void modify(int p, int l, int r, int nl, int nr, int v) {
    if (nl <= l && r <= nr)
        color(p, v);
    else {
        pushdown(p);
        int mid = l + z[z[p].l].size;
        if (nl < mid)
            modify(z[p].l, l, mid - 1, nl, nr, v);
        if (mid < nr)
            modify(z[p].r, mid + 1, r, nl, nr, v);
        if (nl <= mid && mid <= nr)
            z[p].value += v;
        pushup(p);
    }
}
int query(int p, int l, int r, int nl, int nr) {
    if (nl <= l && r <= nr)
        return z[p].sum;
    pushdown(p);
    int mid = l + z[z[p].l].size;
    int res = 0;
    if (nl < mid)
        res += query(z[p].l, l, mid - 1, nl, nr);
    if (mid < nr)
        res += query(z[p].r, mid + 1, r, nl, nr);
    if (nl <= mid && mid <= nr)
        res += z[p].value;
    return res;
}

signed main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) {
        int x;
        scanf ("%d", &x);
        insert(root, i, x);
    }
    while (m --) {
        int opt;
        cin >> opt;
        if (opt == 1) {
            int l, r, k;
            scanf ("%d%d%d", &l, &r, &k);
            modify(root, 1, n, l, r, k);
        } else {
            int k;
            cin >> k;
            printf ("%lld\n", query(root, 1, n, k, k));
        }
    }
    return 0;
}
2024/9/27 09:21
加载中...