SGU 187 Twist and whirl -- want to cheat 6/10

這題挺特別的

因為網路上都說要用Splay Tree

但是其實可以用奇怪的離散化

就是他有很多段都是連續的

（因為相較於 n，m 實在很小）

所以可以直接用這個特性，把他拆成一段一段

一次操作頂多拆出兩段，最多O(m)個

且每次操作是掃過所有的塊體O(m)

所以可以在O(m^2)的時間內完成

但若 m 太大就G掉了

//By momo
#include
#include
#include
#define N 4010
#define FOR(it, c) for(__typeof((c).begin())it=(c).begin();it!=(c).end();it++)
using namespace std;

int n, m, ans[130010];
struct segm{
    int s, e, c;
    segm(){}
    segm(int _s, int _e, int _c){
        s = _s, e = _e, c = _c;
    }
};
list<segm> ls, tp;

void Cut(int x){
    list<segm>::iterator p = ls.begin();
    for(int st = 1; p != ls.end(); p++){
        int en = st + p->e - p->s;
        if(st <= x && x <= en){
            if(p->c){
                int md = p->s + x-st;
                ls.insert(p, segm(p->s, md, 1));
                if(x < en) ls.insert(p, segm(md+1, p->e, 1));
                ls.erase(p);
            }
            else{
                int md = p->e - x+st;
                ls.insert(p, segm(md, p->e, 0));
                if(x < en) ls.insert(p, segm(p->s, md-1, 0));
                ls.erase(p);
            }
            break;
        }
        st = en+1;
    }
}

void Output(){
    list<segm>::iterator p = ls.begin();
    for(int st = 1; p != ls.end(); p++){
        int en = st + p->e - p->s;
        for(int i = st; i <= en; i++){
            if(p->c) ans[i] = p->s + (i-st);
            else ans[i] = p->e - (i-st);
        }
        st = en+1;
    }
    for(int i = 1; i <= n; i++) printf("%d%c", ans[i], i == n?'\n':' ');
}

int main(){
    scanf("%d%d", &n, &m);
    ls.push_back(segm(1, n, 1));
    for(int i = 0; i < m; i++){
        int rl, rr;
        scanf("%d%d", &rl, &rr);
        list<segm>::iterator p, x, y, t;

        Cut(rl-1);
        Cut(rr);

        p = ls.begin();
        for(int st = 1, fir = 1; p != ls.end(); p++){
            int en = st + p->e - p->s;
            if(rl <= st && en <= rr){
                if(fir) x = p, fir = 0;
                y = p;
            }
            st = en+1;
        }

        t = x; t--; y++;
        tp.splice(tp.begin(), ls, x, y);
        t++;

        tp.reverse();
        FOR(it, tp) it->c ^= 1;
        ls.splice(t, tp); tp.clear();
    }
    Output();
}