当前位置：首页 > news >正文

[BZOJ3223]文艺平衡树

news 来源：原创 2024/4/24 0:40:24

题目大意：
　　实现一个数据结构支持区间翻转操作共$n(n\leq100000)$次。

思路：
　　Splay维护区间。
　　对于区间$[l,r]$的翻转可以先将$l-1$旋转到根，再把$r+1$旋转到根的右子结点，此时根结点的右子结点的左子树就是需要翻转的区间。注意翻转过后结点的权值可能不满足二叉搜索树的性质，也不需要满足二叉搜索树的性质。

 1 #include<cstdio>
 2 #include<cctype>
 3 #include<algorithm>
 4 inline int getint() {
 5     register char ch;
 6     while(!isdigit(ch=getchar()));
 7     register int x=ch^'0';
 8     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
 9     return x;
10 }
11 const int N=100003;
12 int n,ans[N];
13 class SplayTree {
14     private:
15         int val[N],par[N],size[N],ch[N][2];
16         bool rev[N];
17         int sz,new_node(const int &x) {
18             val[++sz]=x;
19             size[sz]=1;
20             return sz;
21         }
22         void push_down(const int &p) {
23             if(!rev[p]) return;
24             std::swap(ch[p][0],ch[p][1]);
25             rev[ch[p][0]]^=1;
26             rev[ch[p][1]]^=1;
27             rev[p]=0;
28         }
29         void push_up(const int &p) {
30             size[p]=size[ch[p][0]]+size[ch[p][1]]+1;
31         }
32         void rotate(const int &x) {
33             const int y=par[x],z=par[y];
34             push_down(y),push_down(x);
35             const bool b=x==ch[y][0];
36             par[ch[x][b]=par[ch[y][!b]=ch[x][b]]=y]=x;
37             if(par[x]=z) par[ch[z][ch[z][1]==y]=x]=z;
38             push_up(y),push_up(x);
39         }
40         void splay(int x,const int &goal) {
41             for(register int y=par[x],z=par[y];y!=goal;rotate(x),z=par[y=par[x]]) {
42                 if(z!=goal) rotate((x==ch[y][0])^(y==ch[z][0])?x:y);
43             }
44             if(!goal) root=x;
45         }
46     public:
47         int root;
48         void insert(const int &x) {
49             int y=root;
50             while(ch[y][x>val[y]]) y=ch[y][x>val[y]];
51             par[ch[y][x>val[y]]=new_node(x)]=y;
52             splay(sz,0);
53         }
54         void build(const int &n) {
55             for(register int i=0;i<=n+1;i++) insert(i);
56         }
57         int find(int x) {
58             for(register int y=root;;y=ch[y][size[ch[y][0]]<x]) {
59                 push_down(y);
60                 if(par[y]&&y==ch[par[y]][1]) x-=size[ch[par[y]][0]]+1;
61                 if(size[ch[y][0]]==x) return y;
62             }
63         }
64         void reverse(const int &l,const int &r) {
65             splay(find(l-1),0);
66             splay(find(r+1),root);
67             rev[ch[ch[root][1]][0]]^=1;
68         }
69         void dfs(const int &p) {
70             push_down(p);
71             if(ch[p][0]) dfs(ch[p][0]);
72             if(val[p]&&val[p]<=n) ans[++ans[0]]=val[p];
73             if(ch[p][1]) dfs(ch[p][1]);
74         }
75 };
76 SplayTree t;
77 int main() {
78     t.build(n=getint());
79     for(register int i=getint();i;i--) {
80         const int l=getint(),r=getint();
81         t.reverse(l,r);
82     }
83     t.dfs(t.root);
84     for(register int i=1;i<=n;i++) printf("%d ",ans[i]);
85     return 0;
86 }