无旋Treap求调

RT，调了两天没调出来

#include <bits/stdc++.h>
#define rank rnk
#define mod 20130426
using namespace std;

struct node
{
    int val, size, rnd, cnt, lazy;
    int ch[2];
}t[1000100];

int cnt, rt;

int newnode(int val)
{
    cnt++;
    t[cnt].cnt = t[cnt].size = 1;
    t[cnt].rnd = rand();
    t[cnt].val = val;
    return cnt;
}

void update(int id)
{
    t[id].size = t[t[id].ch[0]].size + t[t[id].ch[1]].size + t[id].cnt;
    return;
}

void pushdown(int id)
{
    if(t[id].lazy)
    {
        t[t[id].ch[0]].lazy ^= 1;
        t[t[id].ch[1]].lazy ^= 1;
        swap(t[id].ch[0], t[id].ch[1]);
        t[id].lazy = 0;
    }
}

int merge(int x, int y)
{
    if(!x || !y)return x + y;
    pushdown(x);
    pushdown(y);
    if(t[x].rnd <= t[y].rnd)
    {
        pushdown(x);
        t[x].ch[1] = merge(t[x].ch[1], y);
        update(x);
        return x;
    }
    else
    {
        pushdown(y);
        t[y].ch[0] = merge(x, t[y].ch[0]);
        update(y);
        return y;
    }
}

void splitk(int k, int id, int &x, int &y)
{
    if(id == 0)
    {
        x = y = 0;
        return;
    }
    int lsize = t[t[id].ch[0]].size;
    pushdown(id);
    if(lsize >= k)
    {
        y = id;
        pushdown(y);
        splitk(k, t[y].ch[0], x, t[y].ch[0]);       
    }
    else
    {
        x = id;
        pushdown(x);
        splitk(k - lsize - 1, t[x].ch[1], t[x].ch[1], y);
    }
    update(id);
}

void query(int id)
{
    if(id == 0)return;
    pushdown(id);
    query(t[id].ch[0]);
    cout << t[id].val << " ";
    query(t[id].ch[1]);
}
void reverse(int l, int r)
{
    int x = 0, y = 0, z = 0;
    splitk(rt, l, x, y);
    splitk(y, r - l + 1, y, z);
    t[y].lazy ^= 1;
    rt = merge(merge(x, y), z);
}

signed main()
{
    srand(536);
    int n, m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
    {
        rt = merge(rt, newnode(i));
    }
//  cout << rt << "\n";
//  for(int i = 1;i <= n;i++)
//  {
//      cout << t[i].val << " " << t[i].ch[0] << " " << t[i].ch[1] << " " << t[i].size << " " << t[i].lazy << "\n";
//  }
    while(m--)
    {
        int l, r;
        cin >> l >> r;
        reverse(l, r);
//      cout << rt << "\n";
//      for(int i = 1;i <= n;i++)
//      {
//          cout << t[i].val << " " << t[i].ch[0] << " " << t[i].ch[1] << " " << t[i].size << " " << t[i].lazy << "\n";
//      }
    }
    query(rt);
    return 0;
}