SWAPPER INFORMATICS

#include <bits/stdc++.h>

#define ll long long
using namespace std;

const int INF = 1e9 + 7;
const int MXN = 1e5 + 7;

struct treap {
    ll cnt, prior;
    ll value, sum;
    treap *l, *r;

    treap() {}
    treap(ll v)
    {
        value = v;
        prior = rand() % MXN;
        l = r = NULL;
        cnt = 1;
        sum = v;
    }
};

typedef treap* tree;

tree root_odd, root_even;
ll n, m;

ll getsum(tree t) {
    return t ? t -> sum : 0;
}

ll get(tree t) {
    return t ? t -> cnt : 0;
}

void upd(tree t) {
    if (!t)
        return;

    t -> cnt = get(t -> l) + get(t -> r) + 1;
    t -> sum = getsum(t -> l) + getsum(t -> r) + t -> value;
}

tree treap_merge(tree a, tree b) {
    upd(a);
    upd(b);

    if (!a || !b)
        return a ? a : b;

    tree tmp;
    if (a -> prior > b -> prior) {
        tmp = a;
        tmp -> r = treap_merge(tmp -> r, b);
    }
    else {
        tmp = b;
        tmp -> l = treap_merge(a, tmp -> l);
    }
    upd(tmp);
    return tmp;
}

void treap_split(tree t, ll k, tree &l, tree &r) {
    if (!t) {
        l = r = NULL;
        return;
    }
    upd(t);
    if (k <= get(t -> l))
        treap_split(t -> l, k, l, t -> l), r = t;
    else
        treap_split(t -> r, k - get(t -> l) - 1, t -> r, r), l = t;

    upd(l);
    upd(r);
}

void print(tree v) {
    if (!v)
        return;

    print(v -> l);
    printf("%lld ", v -> value);
    print(v -> r);
}

ll get_odd_sum(ll l, ll r) {
    if (l > r)
        return 0;

    tree L, R, M;

    treap_split(root_odd, r, L, R);
    treap_split(L, l - 1, L, M);

    ll tmp = M -> sum;
    root_odd = treap_merge(treap_merge(L, M), R);

    return tmp;
}

ll get_even_sum(ll l, ll r) {
    if (l > r)
        return 0;

    tree L, R, M;

    treap_split(root_even, r, L, R);
    treap_split(L, l - 1, L, M);

    ll tmp = M -> sum;
    root_even = treap_merge(treap_merge(L, M), R);

    return tmp;
}

int main() {
    scanf("%lld%lld", &n, &m);
    for (int i = 0; i < n; i++)
    {
        ll x;
        scanf("%lld", &x);
        if (i & 1)
            root_even = treap_merge(root_even, new treap(x));
        else
            root_odd = treap_merge(root_odd, new treap(x));
    }
    printf("Swapper 1:\n");
    for (int i = 0; i < m; i++)
    {
        ll q, x, y, le, re, lo, ro;
        scanf("%lld%lld%lld", &q, &x, &y);

        le = (x - 1) / 2 + 1;
        re = y / 2;

        lo = x / 2 + 1;
        ro = (y + 1) / 2;

        if (q == 1)
        {
            tree LE, RE, ME;
            tree LO, RO, MO;

            treap_split(root_even, re, LE, RE);
            treap_split(LE, le - 1, LE, ME);

            treap_split(root_odd, ro, LO, RO);
            treap_split(LO, lo - 1, LO, MO);

            root_even = treap_merge(treap_merge(LE, MO), RE);
            root_odd = treap_merge(treap_merge(LO, ME), RO);
        }
        else printf("%lld\n", get_odd_sum(lo, ro) + get_even_sum(le, re));
    }
    return 0;
}