FHQ Treap TLE

求助！FHQ Treap TLE 了，不知道是怎么回事。

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <utility>

using namespace std;

struct node {
    node *lc, *rc;
    int index, w, value;
    int tag;
};

static node *
create_node(int index, int value) {
    static node pool[100000], *pos = pool;
    node *ret = pos++;
    *ret = { 0, 0, index, rand(), value, 0 };
    return ret;
}

static void
spread(node *p) {
    if (!p || !p->tag) return;
    p->index = p->tag - p->index;
    swap(p->lc, p->rc);
    if (p->lc) {
        spread(p->lc);
        p->lc->tag = p->tag;
    }
    if (p->rc) {
        spread(p->rc);
        p->rc->tag = p->tag;
    }
    p->tag = 0;
}

static pair<node *, node *>
split(node *p, int b) {
    if (!p) return { 0, 0 };
    spread(p);
    if (p->index < b) {
        auto tmp = split(p->rc, b);
        p->rc = tmp.first;
        return { p, tmp.second };
    } else {
        auto tmp = split(p->lc, b);
        p->lc = tmp.second;
        return { tmp.first, p };  
    }
}

static node *
merge(node *a, node *b) {
    if (!a || !b) return a ? a : b;
    spread(a), spread(b);
    if (a->w > b->w) swap(a, b);
    if (b->index < a->index) {
        auto tmp = b->rc;
        b->rc = 0;
        a->lc = merge(a->lc, b);
        return merge(a, tmp);
    } else {
        auto tmp = b->lc;
        b->lc = 0;
        a->rc = merge(a->rc, b);
        return merge(a, tmp);
    }
}

static int
query(node *p, int index) {
    if (!p) throw "omg";
    spread(p);
    if (index == p->index) return p->value;
    else if (index < p->index) return query(p->lc, index);
    else return query(p->rc, index);
}

int
main() {
    srand(time(0));
    int n, m;
    scanf("%d%d", &n, &m);
    node *root = nullptr;
    for (int i = 1; i <= n; i++)
        root = merge(root, create_node(i, i));
    while (m--) {
        int l, r;
        scanf("%d%d", &l, &r);
        auto t1 = split(root, l);
        auto t2 = split(t1.second, r + 1);
        spread(t2.first);
        t2.first->tag = l + r;
        root = merge(t2.first, merge(t2.second, t1.first));
    }
    for (int i = 1; i <= n; i++)
        printf("%d ", query(root, i));
    puts("");
}