Description

您需要写一种数据结构 (可参考题目标题), 来维护一个有序数列, 其中需要提供以下操作:

翻转一个区间, 例如原有序序列是 54321, 翻转区间是 \([2,4]\) 的话, 结果是 52341

Input

第一行为 \(n, m\),\(n\) 表示初始序列有 \(n\) 个数, 这个序列依次是 \((1, 2, ..., n - 1, n)\);\(m\) 表示翻转操作次数, 接下来 \(m\) 行每行两个数 \([l,r]\).

数据保证 \(1 \leq l \leq r \leq n\).

Output

输出一行 \(n\) 个数字, 表示原始序列经过 \(m\) 次变换后的结果

Sample Input

7 5
3 6
2 4
1 4
6 7
3 5

Sample Output

2 6 4 1 5 7 3

Data Range

对于所有的数据, 满足:\(n, m \leq 10^5\)

Explanation

没有调就直接把 Splay 写挂了一次 (好在没交)

第一次搞错了 find() 函数, 把判断是否应该转移到左子节点的条件语句的大于等于号写成了大于号 (导致所有东西输出都是 \(0\), 然后统一把修改转到空节点上)

第二次发现 clean_lazy() 函数, 就是那个用来最后去掉 lazy 的函数爆栈了, 也就是深度过高, 发现是一个无限递归. 用 xmpaint 调试了一下发现树上出现了环, 然后就瞎搞了 一发把在 find() 的时候同时更新 lazy, 这样就把手算的那组样例数据过掉了 (发现 题目给的原始数据实在是太水了, 所以本题解里的不是原始数据, 更强化了一点)

然后交到大视野上 1A (一遍交 A 一道 Splay 实在是好开心)

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
#define range(_begin,_end) rep(_,_begin,_end)
using namespace std;
typedef long long lli;
const int maxn = 200100;
const int infinit = 10e7;

class SplayTree
{
public:
    int ch[maxn][2], par[maxn];
    int val[maxn], rev[maxn], size[maxn];
    int root, ncnt;
    #define lc(__x) ch[__x][0 ^ rev[__x]]
    #define rc(__x) ch[__x][1 ^ rev[__x]]
    int make_node(int v)
    {
        int p = ++ncnt;
        lc(p) = rc(p) = par[p] = 0;
        val[p] = v; rev[p] = false; size[p] = 1;
        return p;
    }
    void dispatch_lazy(int p)
    {
        if (rev[p]) { range(0,1)
            if (ch[p][_]) rev[ch[p][_]] ^= 1;
            swap(lc(p), rc(p));
            rev[p] = false;
        }
        return ;
    }
    void rotate(int p)
    {
        int q = par[p], g = par[q];
        dispatch_lazy(q);
        dispatch_lazy(p);
        int x = p == rc(q), y = q == rc(g);
        ch[q][x] = ch[p][!x]; if (ch[q][x]) par[ch[q][x]] = q;
        ch[p][!x] = q; par[q] = p;
        if (g) ch[g][y] = p; par[p] = g;
        size[q] = size[lc(q)] + size[rc(q)] + 1;
        size[p] = size[lc(p)] + size[rc(p)] + 1;
        return ;
    }
    void splay(int p, int t)
    {
        for (int q = 0; (q = par[p]) && q != t; rotate(p))
            if (par[q] && par[q] != t)
                rotate((p == rc(q)) == (q == rc(par[q])) ? q : p);
        if (t == 0) root = p;
        return ;
    }
    int find(int sz)
    {
        int p = root;
        while (p) {
            dispatch_lazy(p);
            if (sz <= size[lc(p)]) {
                p = lc(p); continue; }
            sz -= size[lc(p)];
            if (sz == 1) return p;
            sz--; p = rc(p);
        }
        return p;
    }
    void reverse(int l, int r)
    {
        int p = find(l), q = find(r + 2);
        splay(p, 0);
        splay(q, p);
        rev[lc(q)] ^= 1;
        return ;
    }
    void insert(int l, int v)
    {
        int p = find(l + 1), q = find(l + 2);
        splay(p, 0);
        splay(q, p);
        int r = make_node(v);
        par[r] = q; lc(q) = r;
        size[q]++, size[p]++;
        splay(r, 0);
        return ;
    }
    void init(void)
    {
        root = make_node(0);
        rc(root) = make_node(0);
        par[rc(root)] = root;
        size[root] = 2;
        return ;
    }
public:
    void clean_lazy(int p) {
        dispatch_lazy(p);
        range(0,1) if (ch[p][_]) clean_lazy(ch[p][_]);
        return ; }
    void clean_lazy(void) { clean_lazy(root); }
    void export_data(int& acnt, int arr[], int p) {
        if (lc(p)) export_data(acnt, arr, lc(p));
        arr[acnt++] = val[p];
        if (rc(p)) export_data(acnt, arr, rc(p));
        return ; }
    void export_data(int arr[]) { int __ = 0; export_data(__, arr, root); }
} st;

int n, m;
int arr[maxn];

int main(int argc, char** argv)
{
    scanf("%d%d", &n, &m);
    st.init();
    for (int i = 1; i <= n; i++)
        st.insert(i - 1, i);
    for (int i = 1, a, b; i <= m; i++) {
        scanf("%d%d", &a, &b);
        st.reverse(a, b);
    }
    st.clean_lazy();
    st.export_data(arr);
    for (int i = 1; i <= n; i++)
        printf("%d ", arr[i]);
    return 0;
}