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;
}