题目链接: https://www.luogu.com.cn/problem/P3391
您需要写一种数据结构 (可参考题目标题), 来维护一个有序数列.
其中需要提供以下操作: 翻转一个区间, 例如原有序序列是 \(5\ 4\ 3\ 2\ 1\), 翻转区间是 \([2,4]\) 的话, 结果是 \(5\ 2\ 3\ 4\ 1\).
思路
Splay 模板. 总算是会抠 Splay 了.
Treap 采用键值随机化来维护 BST 平衡, 而 Splay 则采用旋转来维护 BST 平衡. 基本上每进行一次关于 \(x\) 的操作, 就把 \(x\) 旋转至树根.
对于区间旋转的操作, 我们以下标建立一棵 Splay, 对于旋转 \([l,r]\), 我们将 \(l\) 的前驱旋转至树根,\(r\) 的后继旋转至树根的右子节点, 那么此时 \(r\) 的后继的左子树即为 \([l,r]\).
那么就把 \(r\) 后继的左子树的树根打上一个懒惰标记, 下次旋转该点时就将该点的左右子树互换, 类似线段树的标记下传.
时间复杂度不会证.
代码
这份代码还有很多地方可以简化, 但是太懒了.
- #include <cstdio>
- #include <cstring>
- #include <algorithm>
- using namespace std;
- const int N=100010,Inf=2e9;
- int n,Q,rt;
- struct Splay
- {
- int tot,val[N],fa[N],son[N][2],cnt[N],size[N];
- bool tag[N];
- void pushup(int x)
- {
- size[x]=size[son[x][1]]+size[son[x][0]]+cnt[x];
- }
- void pushdown(int x)
- {
- if (tag[x])
- {
- tag[son[x][0]]^=1; tag[son[x][1]]^=1;
- swap(son[x][0],son[x][1]);
- tag[x]=0;
- }
- }
- bool pos(int x)
- {
- return x==son[fa[x]][1];
- }
- void build()
- {
- tot=2; rt=1;
- val[1]=-Inf; val[2]=Inf;
- fa[2]=1; son[1][1]=2;
- cnt[1]=cnt[2]=1;
- pushup(2); pushup(1);
- }
- void rotate(int x)
- {
- pushdown(x);
- int y=fa[x],z=fa[y],k=pos(x),c=son[x][k^1];
- fa[c]=y; son[y][k]=c;
- fa[x]=z; son[z][pos(y)]=x;
- fa[y]=x; son[x][k^1]=y;
- pushup(y); pushup(x);
- }
- void splay(int x,int f=0)
- {
- while (fa[x]!=f)
- {
- int y=fa[x],z=fa[y];
- if (z!=f)
- {
- if (pos(x)==pos(y)) rotate(y);
- else rotate(x);
- }
- rotate(x);
- }
- if (!f) rt=x;
- }
- void ins(int x)
- {
- int p=rt,f=0;
- while (p && val[p]!=x)
- {
- f=p;
- if (val[p]<x) p=son[p][1];
- else p=son[p][0];
- }
- if (val[p]==x) cnt[p]++;
- else
- {
- p=++tot;
- val[p]=x; cnt[p]=size[p]=1;
- fa[p]=f; son[f][x>val[f]]=p;
- }
- pushup(p); pushup(f);
- splay(p);
- }
- int get_val(int k)
- {
- int p=rt;
- while (1)
- {
- pushdown(p);
- if (size[son[p][0]]>=k) p=son[p][0];
- else if (k<=size[son[p][0]]+cnt[p]) break;
- else k-=size[son[p][0]]+cnt[p],p=son[p][1];
- }
- splay(p);
- return p;
- }
- void reverse(int l,int r)
- {
- int p=get_val(l),q=get_val(r+2);
- splay(p);
- splay(q,p);
- tag[son[q][0]]^=1;
- }
- }splay;
- void dfs(int x)
- {
- if (!x) return;
- splay.pushdown(x);
- dfs(splay.son[x][0]);
- if (x>2) printf("%d",splay.val[x]);
- dfs(splay.son[x][1]);
- }
- int main()
- {
- scanf("%d%d",&n,&Q);
- splay.build();
- for (int i=1;i<=n;i++)
- splay.ins(i);
- while (Q--)
- {
- int l,r;
- scanf("%d%d",&l,&r);
- splay.reverse(l,r);
- }
- dfs(rt);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3462033.html