洛谷 P3391 【模板】文艺平衡树（Splay）

Description

• 您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1

Input

• 第一行为n,m。n表示初始序列有n个数，这个序列依次是(1,2,⋯n−1,n) (1,2, …, n-1,n), m表示翻转操作次数。接下来m行每行两个数 [l,r] 数据保证 1≤l≤r≤n

Output

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

Sample Input

5 31 31 31 4

Sample Output

4 3 2 1 5

Data Size

• n,m≤100000

题解：

• fhq-treap。按大小分裂。
• fhq-treap真的强，代码恰好百行解决（没压行。还说什么，膜fhq大佬啊！
• emmm…..再次强调，按大小分裂的fhq-treap中的val是序列下标，这样中序遍历的结果是val的递增，这恰好就保证了是序列递增！也就是输出序列！
• 翻转操作用懒标记思想，如果一个点的儿子有风险被篡改，就下传一下标记。
• 想操作区间[l, r]的话，先分裂成前(i - 1)为x树，剩下的为y树。再在y树中分裂前(r - l + 1)为y树，剩下的为z树。那么y树代表[l, r]区间。最后别忘了合并起来。

#include 
    
     #include 
     
      #include 
      
       #define N 100005using namespace std;struct T {int l, r, val, dat, size, tag;} t[N];int n, q, root, tot, x, y, z;int read(){    int x = 0; char c = getchar();    while(c < '0' || c > '9') c = getchar();    while(c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}    return x;}int New(int val){    t[++tot].val = val;    t[tot].dat = rand();    t[tot].size = 1;    return tot;}void up(int p) {t[p].size = t[t[p].l].size + t[t[p].r].size + 1;}void down(int p){    swap(t[p].l, t[p].r);    t[t[p].l].tag ^= 1;    t[t[p].r].tag ^= 1;    t[p].tag = 0;}int merge(int x, int y){    if(!x || !y) return x + y;    if(t[x].dat > t[y].dat)    {        if(t[x].tag) down(x);        t[x].r = merge(t[x].r, y);        up(x); return x;    }    else    {        if(t[y].tag) down(y);        t[y].l = merge(x, t[y].l);        up(y); return y;    }}void split(int p, int size, int &x, int &y){    if(!p) {x = y = 0; return;}    if(t[p].tag) down(p);    if(t[t[p].l].size + 1 <= size)    {        x = p;        split(t[p].r, size - t[t[p].l].size - 1, t[p].r, y);    }    else    {        y = p;        split(t[p].l, size, x, t[p].l);    }    up(p);}void reverse(int l, int r){    split(root, l - 1, x, y);    split(y, r - l + 1, y, z);    t[y].tag ^= 1;    root = merge(x, merge(y, z));}void dfs(int p){    if(!p) return;    if(t[p].tag) down(p);    dfs(t[p].l);    printf("%d ", t[p].val);    dfs(t[p].r);}int main(){    cin >> n >> q;    for(int i = 1; i <= n; i++)        root = merge(root, New(i));    for(int i = 1; i <= q; i++)    {        int l = read(), r = read();        reverse(l, r);    }    dfs(root);    return 0;}