# BZOJ3223: Artful SBT

Problem Description: Given a sequence comprised of numbers from 1 – N in order. There are M operations. Each operation will flip a sequence [l,r]. Please output the finally formed sequence.

Input Format:
One line with the number N and M.
The next M lines contain two numbers l and r.

Output Format:
The sequence after M operations.

Sample Input:
5 3 1 3 1 3 1 4

Sample Output:
4 3 2 1 5

Solution: Emm.. A classical Splay Tree problem. Just try to accomplish the lazy-tag that will represent the flipping operation on a parent and pass it down to achieve the flipping of the entire subtree. One thing to remember is that by rotating x to the root and y to the right child of the root, we can have the range from x + 1 to y – 1 as the left subtree of the y node.

#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <stdio.h>
#include <fstream>
#include <cmath>
#include <stdlib.h>
#include <iomanip>
#include <algorithm>
#include <limits.h>
#include <stack>
using namespace std;
#define FAST_IO ios::sync_with_stdio(false);
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<double,double> pdd;
typedef long long ll;
const int maxn = 1e6 + 5;
int N,M,ch[maxn][2],fa[maxn],rev[maxn],val[maxn],sz[maxn],root,tot;

void pushup(int x){
sz[x] = sz[ch[x][0]] + sz[ch[x][1]] + 1;
}
void pushdown(int x){
if(rev[x]){
rev[x] = 0;
rev[ch[x][0]] ^= 1;
rev[ch[x][1]] ^= 1;
swap(ch[ch[x][0]][0],ch[ch[x][0]][1]);
swap(ch[ch[x][1]][0],ch[ch[x][1]][1]);
}
}

void rotate(int x){
int f = fa[x];
bool k = (ch[fa[x]][1] == x);
ch[f][k] = ch[x][!k];
ch[x][!k] = f;
ch[fa[f]][ch[fa[f]][1] == f] = x;
fa[x] = fa[f];
fa[ch[f][k]] = f;
fa[f] = x;
pushup(f);
pushup(x);
}

void splay(int x,int g){
while(fa[x] != g) rotate(x);
if(!g) root = x;
}
int kth(int cur,int k){
pushdown(cur);
if(k <= sz[ch[cur][0]]) return kth(ch[cur][0],k);
else if(k == sz[ch[cur][0]] + 1) return cur;
else return kth(ch[cur][1],k - 1 - sz[ch[cur][0]]);
}
int build(int l,int r,int rt){
if(l > r) return 0;
int now = ++tot;
int mid = (l + r) >> 1;
val[now] = mid;
ch[now][0] = build(l,mid - 1,now);
ch[now][1] = build(mid + 1,r,now);
fa[now] = rt;
pushup(now);
return now;
}

void update(int l,int r){
int x,y,t;
x = kth(root,l - 1);
splay(x,0);
y = kth(root,r + 1);
splay(y,x);
t = ch[y][0];
swap(ch[t][0],ch[t][1]);
rev[t] ^= 1;
}

void output(int x){
if(!x) return ;
pushdown(x);
output(ch[x][0]);
cout<<val[x]<<" ";
output(ch[x][1]);
}
int main(){
FAST_IO
cin>>N>>M;
root = build(0,N + 1,0);
for(int i = 1; i <= M; i++){
int l,r;
cin>>l>>r;
update(l + 1,r + 1);
}
splay(kth(root,1),0);
splay(kth(root,N + 2),root);
output(ch[ch[root][1]][0]);
return 0;
}