「BZOJ3223」JoyOI 1729 文艺平衡树
Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：翻转一个区间，例如原有序序列是5 4 3 2 1，翻转区间是[2,4]的话，结果是5 2 3 4 1
Input
第一行为n,m n表示初始序列有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
HINT
N,M<=100000
题解
4：22 *1
7：22 *1
直接splay。。。 区间翻转而已。。。
|
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 |
#include<iostream> #include<cstdio> using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,sz,rt; int fa[100005],c[100005][2],id[100005]; int size[100005]; bool rev[100005]; void pushup(int k) { int l=c[k][0],r=c[k][1]; size[k]=size[l]+size[r]+1; } void pushdown(int k) { int l=c[k][0],r=c[k][1]; if(rev[k]) { swap(c[k][0],c[k][1]); rev[l]^=1;rev[r]^=1; rev[k]=0; } } void rotate(int x,int &k) { int y=fa[x],z=fa[y],l,r; if(c[y][0]==x)l=0;else l=1;r=l^1; if(y==k)k=x; else {if(c[z][0]==y)c[z][0]=x;else c[z][1]=x;} fa[x]=z;fa[y]=x;fa[c[x][r]]=y; c[y][l]=c[x][r];c[x][r]=y; pushup(y);pushup(x); } void splay(int x,int &k) { while(x!=k) { int y=fa[x],z=fa[y]; if(y!=k) { if(c[y][0]==x^c[z][0]==y)rotate(x,k); else rotate(y,k); } rotate(x,k); } } int find(int k,int rank) { pushdown(k); int l=c[k][0],r=c[k][1]; if(size[l]+1==rank)return k; else if(size[l]>=rank)return find(l,rank); else return find(r,rank-size[l]-1); } void rever(int l,int r) { int x=find(rt,l),y=find(rt,r+2); splay(x,rt);splay(y,c[x][1]); int z=c[y][0]; rev[z]^=1; } void build(int l,int r,int f) { if(l>r)return; int now=id[l],last=id[f]; if(l==r) { fa[now]=last;size[now]=1; if(l<f)c[last][0]=now; else c[last][1]=now; return; } int mid=(l+r)>>1;now=id[mid]; build(l,mid-1,mid);build(mid+1,r,mid); fa[now]=last;pushup(mid); if(mid<f)c[last][0]=now; else c[last][1]=now; } int main() { n=read();m=read(); for(int i=1;i<=n+2;i++) id[i]=++sz; build(1,n+2,0);rt=(n+3)>>1; for(int i=1;i<=m;i++) { int l=read(),r=read(); rever(l,r); } for(int i=2;i<=n+1;i++) printf("%d ",find(rt,i)-1); return 0; } |
计数器 9787169
OI 课件=>
OI 课件=>
求教，翻转区间后中序遍历得到的应该不是递增的吧…
这样没有破坏splay的性质吗?
splay维护的是位序
id数组是不是为了省空间啊
求问黄学长，为什么有区间翻转操作的时候，splay不需要pushdown…做这类题一直搞不懂
因为find的时候pushdown了
学长，你为什要建1..n + 2 区间的Splay树，而并不是1..n
帮学长回答一下。。。1和n+2是两侧的哨兵节点，这样就可以在访问2..n+1区间（左右边界）的时候提起0和n+2节点。
黄学长，你的SPLAY中的splay和rotate都是传的两个参数，如果现在要进行启发式合并（也就是有多棵Splay，有许多根），那么int &k那里肯定要传的是当前结点所在的Splay的根。怎么维护这个根结点啊？？
你肯定要用个数组把splay的根存起来呗
为什么rever中是y=find(rt,r+2);？
要操作l+1到r+1这段，把l转到根，r+2转到根的右儿子
原来是酱紫，懂了
请问黄学长加了两个虚根为什么只加1？
你要操作1，n这个序列，需要对0和n+1作旋转
看黄学长主页学过来的
那个find函数到底是find什么鬼
找K大，即序列第K个数
也就是说现在不满足二叉搜索树的性质是吗
序列顺序与大小关系不可同时维护
这样不是序列顺序和大小关系都不满足二叉搜索树吗
序列编号满足
好像大概明白了，谢谢黄学长
一直不理解id数组到底是什么含义。。
噢这题是没用的
那在一般的序列维护题目里面id数组是什么含义？
详见维修数列