FHQ treap写法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <random>
std::mt19937 rnd(233);
using namespace std;
const int N = 100005;
struct Node
{
int l, r;
int key, val;
int size;
bool rev;
}tr[N];
int n, m;
int root, idx;
int newnode(int key)
{
tr[++ idx].key = key;
tr[idx].val = rnd();
tr[idx].size = 1;
return idx;
}
void pushdown(int u)
{
if(tr[u].rev)
{
swap(tr[u].l, tr[u].r);
tr[tr[u].l].rev ^= 1;
tr[tr[u].r].rev ^= 1;
tr[u].rev = 0;
}
}
void pushup(int u)
{
tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
}
int merge(int x, int y)
{
if(!x || !y) return x + y;
if(tr[x].val < tr[y].val)
{
pushdown(x);
tr[x].r = merge(tr[x].r, y);
pushup(x);
return x;
}
else
{
pushdown(y);
tr[y].l = merge(x, tr[y].l);
pushup(y);
return y;
}
}
void split(int u, int siz, int &x, int &y)
{
if(!u) x = y = 0;
else
{
pushdown(u);
if(tr[tr[u].l].size + 1 <= siz)
{
x = u;
split(tr[u].r, siz - (tr[tr[u].l].size + 1), tr[u].r, y);
}
else
{
y = u;
split(tr[u].l, siz, x, tr[u].l);
}
pushup(u);
}
}
void modify(int l, int r)
{
int x, y, z;
split(root, l - 1, x, y);
split(y, r - l + 1, y, z);
tr[y].rev ^= 1;
root = merge(merge(x, y), z);
}
void dfs(int u)
{
if(!u) return;
pushdown(u);
dfs(tr[u].l);
printf("%d ", tr[u].key);
dfs(tr[u].r);
}
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i ++ )
root = merge(root, newnode(i));
while (m -- )
{
int l, r;
scanf("%d%d", &l, &r);
modify(l, r);
}
dfs(root);
return 0;
}
orz