题目传送门

sol:第一次看题还真信了是用线段树来做，但是没什么想法，看了题解发现是我不会的Treap，然后花了几天时间学习了一下并补掉题目

无旋Treap

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int MAXN = 2e5 + ;

struct Treap {

    int ls, rs;

    int rand, size;

    LL sum, val, lazy;

} node[MAXN];

int root, tot;

int add_node(int v) {

    int i = ++tot;

    node[i].ls = node[i].rs = ;

    node[i].rand = rand();

    node[i].sum = node[i].val = v;

    node[i].lazy = ;

    node[i].size = ;

    return i;

}

void push_down(int rt) {

    int ls = node[rt].ls;

    int rs = node[rt].rs;

    if (ls != ) {

        node[ls].lazy += node[rt].lazy;

        node[ls].val += node[rt].lazy;

        node[ls].sum += node[ls].size * node[rt].lazy;

    }

    if (rs != ) {

        node[rs].lazy += node[rt].lazy;

        node[rs].val += node[rt].lazy;

        node[rs].sum += node[rs].size * node[rt].lazy;

    }

    node[rt].lazy = ;

}

void push_up(int rt) {

    int ls = node[rt].ls;

    int rs = node[rt].rs;

    node[rt].size = node[ls].size + node[rs].size + ;

    node[rt].sum = node[ls].sum + node[rs].sum + node[rt].val;

}

void split(int rt, int& a, int& b, int s) {

    if (rt == ) {

        a = b = ;

        return;

    }

    push_down(rt);

    int size = node[node[rt].ls].size;

    if (size < s) {

        a = rt;

        split(node[rt].rs, node[a].rs, b, s - size - );

    } else {

        b = rt;

        split(node[rt].ls, a, node[b].ls, s);

    }

    push_up(rt);

}

void merge(int& rt, int a, int b) {

    if (a ==  || b == ) {

        rt = a + b;

        return;

    }

    push_down(a);

    push_down(b);

    if (node[a].rand < node[b].rand) {

        rt = a;

        merge(node[rt].rs, node[a].rs, b);

    } else {

        rt = b;

        merge(node[rt].ls, a, node[b].ls);

    }

    push_up(rt);

}

void insert(int p, int v) {

    int x = , y = ;

    split(root, x, y, p - );

    merge(root, x, add_node(v));

    merge(root, root, y);

}

void add(int l, int r, int v) {

    int x = , y = , z = ;

    split(root, root, z, r);

    split(root, x, y, l - );

    node[y].lazy += v;

    node[y].val += v;

    node[y].sum += node[y].size * v;

    merge(root, x, y);

    merge(root, root, z);

}

LL query(int l, int r) {

    int x = , y = , z = ;

    split(root, root, z, r);

    split(root, x, y, l - );

    LL sum = node[y].sum;

    merge(root, x, y);

    merge(root, root, z);

    return sum;

}

int main() {

    int n, q;

    scanf("%d", &n);

    for (int i = ; i <= n; i++) {

        int v; scanf("%d", &v);

        merge(root, root, add_node(v));

    }

    scanf("%d", &q);

    for (int i = ; i <= q; i++) {

        int opt; scanf("%d", &opt);

        if (opt == ) {

            int pos; scanf("%d", &pos);

            insert(pos, );

        } else if (opt == ) {

            int l, r, v;

            scanf("%d%d%d", &l, &r, &v);

            add(l, r, v);

        } else {

            int l, r;

            scanf("%d%d", &l, &r);

            printf("%lld\n", query(l, r));

        }

    }

    return ;

}

在前置知识都掌握的情况下Treap还是挺好懂的，而且之前感觉lazy标记挺乱的，看了这题之后感觉理清了

巴特西

牛客-Forsaken的数列（Treap）

题目传送门

最新文章

热门文章