Декартово (*=-1, reverse)

struct node {
    node *l, *r;
    int x, y, sz;
    bool mult;
    bool rev;
    node(int key)
    {
        mult = false;
        rev = false;
        x = key;
        y = rand();
        l = 0;
        r = 0;
        sz = 1;
    }
};

int get_sz(node * a)
{
    if (a == 0)
        return 0;
    return a->sz;
}

void update(node * a)
{
    if (a == 0)
    {
        return;
    }
    a->sz = 1 + get_sz(a->r) + get_sz(a->l);
    if (a->mult == 1)
    {
        a->x *= -1;
        if (a->l != 0)
            a->l->mult ^= 1;
        if (a->r != 0)
            a->r->mult ^= 1;
        a->mult = 0;
    }
    if (a->rev == 1)
    {
        swap(a->l, a->r);
        if (a->l != 0)
            a->l->rev ^= 1;
        if (a->r != 0)
            a->r->rev ^= 1;
        a->rev = 0;
    }
}

pair<node*, node*> split_k(node * a, int k)
{
    if (a == 0)
    {
        return {0, 0};
    }
    update(a);
    if (get_sz(a->l) >= k)
    {
        auto b = split_k(a->l, k);
        a->l = b.second;
        update(a);
        update(b.first);
        return {b.first, a};
    }
    else
    {
        auto b = split_k(a->r, k - 1 - get_sz(a->l));
        a->r = b.first;
        update(a);
        update(b.second);
        return {a, b.second};
    }
}

node * merge(node *a, node *b)
{
    update(a);
    update(b);
    if (a == 0)
        return b;
    if (b == 0)
        return a;
    if (a->y > b->y)
    {
        a->r = merge(a->r, b);
        update(a);
        return a;
    }
    else
    {
        b->l = merge(a, b->l);
        update(b);
        return b;
    }
}


node * insert(node * a, int r)
{
    node * nk = new node(r);
    return merge(a, nk);
}

void output(node * a)
{
    update(a);
    if (a == 0)
        return;
    output(a->l);
    cerr << a->x << " ";
    output(a->r);
}