「Luogu P3391」【模板】文艺平衡树（Splay）

发表于 |
字数统计: 712 | 阅读时长 ≈ 4

给一个$1$到$n$的排列，每一次能将区间$[l,r]$反转，求最后的排列

链接

题解

实测暴力能，但是不能用暴力，只能老老实实写Splay。
作为一道模板题，还是说一下我犯过的错误吧qwq。
第一，$splay$函数中旋转完了一定要更新$fa$和$x$的信息，由于这个，我居然调了一下午+一晚上。
第二，注意$reverse$中更新信息的语句，又调了一中午。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include<bits/stdc++.h>
#define DEBUG printf("In function %s, line %d\n",__FUNCTION__,__LINE__)
using namespace std;
typedef int ll;
const ll MAXN=2e5+51;
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
ll cnt,qcnt,l,r;
namespace Splay{
    struct Node{
        ll fa,val,size,tag;
        ll ch[2];
        inline void reset(ll val=0,ll fa=0)
        {
            this->fa=fa,this->val=val,this->size=1;
            this->tag=this->ch[0]=this->ch[1]=0;
        }
    };
    struct Splay{
        ll tot,root;
        Node nd[MAXN];
        inline bool id(ll x)
        {
            return nd[nd[x].fa].ch[1]==x;
        }
        inline void update(ll x)
        {
            nd[x].size=nd[nd[x].ch[0]].size+nd[nd[x].ch[1]].size+1;
        }
        inline void spread(ll x)
        {
            if(nd[x].tag)
            {
                nd[nd[x].ch[0]].tag^=1,nd[nd[x].ch[1]].tag^=1;
                nd[x].tag=0;
                swap(nd[x].ch[0],nd[x].ch[1]);
            }
        }
        inline void connect(ll x,ll fa,ll dir)
        {
            nd[x].fa=fa,nd[fa].ch[dir]=x;
        }
        inline void rotate(ll x)
        {
            ll fa=nd[x].fa,gfa=nd[fa].fa,dir=id(x);
            connect(x,gfa,id(fa));
            connect(nd[x].ch[dir^1],fa,dir);
            connect(fa,x,dir^1);
            update(fa),update(x);
        }
        inline void splay(ll cur,ll target)
        {
            while(nd[cur].fa!=target)
            {
                ll fa=nd[cur].fa,gfa=nd[fa].fa;
                if(gfa!=target)
                {
                    rotate(id(cur)^id(fa)?cur:fa);
                }
                rotate(cur);
            }
            if(!target)
            {
                root=cur;
            }
        }
        inline void insert(ll val)
        {
            ll cur=root,fa=0;
            while(cur)
            {
                fa=cur,cur=nd[cur].ch[val>nd[cur].val];
            }
            cur=++tot;
            if(fa)
            {
                nd[fa].ch[val>nd[fa].val]=cur;
            }
            nd[cur].reset(val,fa);
            splay(cur,0);
        }
        inline ll findVal(ll rk)
        {
            ll cur=root;
            while(1)
            {
                spread(cur);
                if(nd[nd[cur].ch[0]].size>=rk)
                {
                    cur=nd[cur].ch[0];
                }
                else
                {
                    if(nd[nd[cur].ch[0]].size+1==rk)
                    {
                        return cur;
                    }
                    else
                    {
                        rk-=nd[nd[cur].ch[0]].size+1,cur=nd[cur].ch[1];
                    }
                }
            }
        }
        inline void reverse(ll l,ll r)
        {
            l=findVal(l),r=findVal(r+2);
            splay(l,0),splay(r,l);
            nd[nd[nd[root].ch[1]].ch[0]].tag^=1;
        }
        inline void op(ll cur)
        {
            spread(cur);
            if(nd[cur].ch[0])
            {
                op(nd[cur].ch[0]);
            }
            if(nd[cur].val>1&&nd[cur].val<cnt+2)
            {
                printf("%d ",nd[cur].val-1);
            }
            if(nd[cur].ch[1])
            {
                op(nd[cur].ch[1]);
            }
        }
    };
}
Splay::Splay splay;
int main()
{
    cnt=read(),qcnt=read();
    for(register int i=1;i<=cnt+2;i++)
    {
        splay.insert(i);
    }
    for(register int i=0;i<qcnt;i++)
    {
        l=read(),r=read();
        splay.reverse(l,r);
    }
    splay.op(splay.root);
}