FHQ Treap 求调。

rt。

#include<bits/stdc++.h>
#define int long long
#define _Dark_Star exit(0)
#define inf 0x3f3f3f3f
#define up(i,x,y) for(register int i=x;i<=y;i++)
#define dn(i,x,y) for(register int i=x;i>=y;i--)
using namespace std;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return x*f;}
inline void write(int x){if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10|48);}
inline void writeln(int x){write(x),putchar('\n');}
inline void writesp(int x){write(x),putchar(' ');}

const int N = 1e5 + 10;

struct node{
  int val , key , size , l , r;
  bool rev;
}tr[N];
int n , root , idx;
int T;

inline int newnode(int v){
  return tr[++idx].val = v , tr[idx].key = rand() , tr[idx].size = 1 , idx;
} inline void pushup(int u){
  tr[u].size = tr[tr[u].l].size + tr[tr[u].r].size + 1;
} inline void pushdown(int u){
  if(tr[u].rev){
    swap(tr[u].l , tr[u].r);
    if(tr[u].l) tr[tr[u].l].rev ^= 1;
    if(tr[u].r) tr[tr[u].r].rev ^= 1;
    tr[u].rev = 0;
  }
} inline void split(int u ,int v,int &x,int &y){
  if(!u){x = y = 0;return;}
  pushdown(u);
  if(tr[u].size < v){
    x = u;
    split(tr[x].r , v - tr[tr[u].l].size - 1, tr[x].r , y);
  }
  else{
    y = u;
    split(tr[y].l , v , x , tr[y].l);
  }
  pushup(u);
} inline int merge(int x,int y){
  if(!x || !y) return x + y;
  if(tr[x].key < tr[y].key){
    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;
  }
} inline void reverse(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(x , merge(y,z));
} inline void print(int rt){
  if(!rt) return;
  pushdown(rt);
  print(tr[rt].l);
  writesp(tr[rt].val);
  print(tr[rt].r);
} signed main(){
  srand(time(0));
  n = read();T = read();
  up(i,1,n) root = merge(root , newnode(i));
  while(T--){
    int L = read() , R = read();
    reverse(L , R); // print(root);puts("");
  }
  print(root);
  _Dark_Star;
}