新技能:splay支持区间翻转,区间插入,区间删除

xiaoxiao2021-02-27  204

splay加两个哨兵左一个,右一个。这样便于提取区间。 建树时就一直放在前一个节点的右儿子即可,然后找一个中间的点splay到根

find操作支持找到区间当前第x位 提取区间:把l-1位上splay到根,第r+1位splay到root的右子树,然后[l,r]就在r+1位的左子树上。

然后具体的:

对于区间翻转: find当前区间那个点时一路pushdown懒标记,懒标记的思想和线段树的那个类似,十分灵活,你的该区间内的点,左边到了右边,右边到了左边,现在只要左右两边都换顺序这就是一种分治思想。懒标记直接打在r+1位的左子树上。

int find(int no,int x) { S[0]=0; pushdown(no); if(S[ch[no][0]]+1==x) return no; if(S[ch[no][0]]>=x) return find(ch[no][0],x); return find(ch[no][1],x-S[ch[no][0]]-1); } void ond() { scanf("%d%d",&l,&r); if(l==r) return; int fl=find(root,l); int fr=find(root,r+2); splay(fl,0); splay(fr,root); lazy[ch[fr][0]]^=1; }

对于区间删除,直接提取后删除,插入就直接提取头指针,中间加一段,然后把原来的拼在后面。

转载请注明原文地址: https://www.6miu.com/read-11880.html

最新回复(0)