Submission #72694520

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define int long long
template <typename Info>
struct Segment_Tree {
    Info *node;

    Segment_Tree(int _n = 0) {
        node = new Info[4 << std::__lg(_n + 1)]();
    }

    void push_up(int p) {
        node[p] = node[p << 1] + node[p << 1 | 1];
    }

    void build(int p, int l, int r, const std::vector<Info> &info) {
        if (l == r)
            return (void)(node[p] = info[l]);
        const int m = (l + r) >> 1;
        build(p << 1, l, m, info);
        build(p << 1 | 1, m + 1, r, info);
        push_up(p);
    }

    void build(int p, int l, int r) {
        if (l == r)
            return (void)(node[p] = Info());
        const int m = (l + r) >> 1;
        build(p << 1, l, m);
        build(p << 1 | 1, m + 1, r);
        push_up(p);
    }

    void update(int p, int l, int r, int u, Info x) {
        if (u < l || r < u)
            return;
        if (l == r)
            return (void)(node[p].update(x));
        const int m = (l + r) >> 1;
        update(p << 1, l, m, u, x);
        update(p << 1 | 1, m + 1, r, u, x);
        push_up(p);
    }

    Info query(int p, int l, int r, int L, int R) {
        if (R < l || r < L)
            return Info();
        if (L <= l && r <= R)
            return node[p];
        const int m = (l + r) >> 1;
        return query(p << 1, l, m, L, R) + query(p << 1 | 1, m + 1, r, L, R);
    }

    template <typename Check>
    std::pair<int, Info> search(int p, int l, int r, int L, int R, Info pre, Check check) {
        if (r < L || R < l) return std::make_pair(-1, Info());
        if (!check(pre + node[p])) return std::make_pair(-1, node[p]);
        if (l == r) return std::make_pair(l, node[p]);
        int mid = (l + r) >> 1;
        auto left_res = search(p << 1, l, mid, L, R, pre, check);
        if (left_res.first == -1) {
            return search(p << 1 | 1, mid + 1, r, L, R, pre + left_res.second, check);
        }
        return left_res;
    }

};
struct info {
    int sum;
    info(int _sum = 0) {
        sum = _sum;

    }
    friend info operator + (info l,info r) {
        info res;
        res.sum = l.sum + r.sum;
        return res;
    }
    void update(info x) {
        *this = x;
    }
};
signed main() {
    int n,q;
    cin >> n >> q;
    vector <info> a(n + 1);
    Segment_Tree<info> seg(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i].sum;
    seg.build(1,1,n,a);
    for(int i=1;i<=q;i++) {
        int op;
        cin >> op;
        if(op == 1) {
            int x;
            cin >> x;
            int t1 = seg.query(1,1,n,x,x).sum;
            int t2 = seg.query(1,1,n,x + 1,x + 1).sum;
            swap(t1,t2);
            seg.update(1,1,n,x,info(t1));
            seg.update(1,1,n,x + 1,info(t2));
        }
        else {
            int l,r;
            cin >> l >> r;
            cout << seg.query(1,1,n,l,r).sum << "\n";
        }
    }
}

Submission Info

Judge Result