P3391 文艺平衡树
发布日期:2021-09-25 23:58:01 浏览次数:12 分类:技术文章

本文共 2723 字,大约阅读时间需要 9 分钟。

功能:实现区间反转
比如当前需要反转 [ l , r ] ,那么只需要把 l - 1 和 r + 1 分别旋到根节点,让后根节点右子树的左子树就是 [ l , r ] 区间内的数,在上面加一个 tag 懒标即可。
注意各个地方pushdown。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define X first#define Y second#define L (u<<1)#define R (u<<1|1)#define Mid (tr[u].l+tr[u].r>>1)#define Len(u) (tr[u].r-tr[u].l+1)#define pb push_back#define mk make_pairusing namespace std;typedef long long LL;typedef pair
PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;const double eps=1e-6;struct Splay{ struct node { int v,father;//v是结点值,father是父亲结点 int ch[2];//ch[0] 左节点 ch[1] 右结点 int sum;//包含自己下面有多少元素(非结点) int recy;//该结点元素出现次数(非结点) int tag;//区间标记 }; node e[N]; int idx; int rot,a[N]; void update(int x)//更新当前结点sum { e[x].sum=e[e[x].ch[0]].sum+e[e[x].ch[1]].sum+e[x].recy; } int identify(int x)//确定当前结点是父亲的左孩子还是右孩子 { return e[e[x].father].ch[0]==x? 0:1; } void connect(int x,int f,int son)//x作为f的son(左右)儿子 { e[x].father=f; e[f].ch[son]=x; } void pushdown(int x)//标记 { if(x&&e[x].tag) { e[e[x].ch[0]].tag^=1; e[e[x].ch[1]].tag^=1; swap(e[x].ch[0],e[x].ch[1]); e[x].tag=0; } } void rotate_tree(int x)//旋转节点 { int y=e[x].father; int mroot=e[y].father; pushdown(x); pushdown(y); int mrootson=identify(y); int yson=identify(x); int B=e[x].ch[yson^1]; connect(B,y,yson); connect(y,x,(yson^1)); connect(x,mroot,mrootson); update(y); update(x); } void splay_tree(int x,int goal)//伸展操作 { for(int t;(t=e[x].father)!=goal;rotate_tree(x)) if(e[t].father!=goal) rotate_tree(identify(x)==identify(t)? t:x); if(goal==0) rot=x; } int build_tree(int l,int r,int fa)//递归建树 { if(l>r) return 0; int mid=l+r>>1; int now=++idx; e[now].father=fa; e[now].ch[0]=e[now].ch[1]=0; e[now].recy++,e[now].sum++; e[now].v=a[mid]; e[now].ch[0]=build_tree(l,mid-1,now); e[now].ch[1]=build_tree(mid+1,r,now); update(now); return now; } int find_tree(int v) { int now=rot; while(1) { pushdown(now); if(v<=e[e[now].ch[0]].sum) now=e[now].ch[0]; else { v-=e[e[now].ch[0]].sum+e[now].recy; if(v<=0) return now; now=e[now].ch[1]; } } return 0; } void reverse(int x,int y) { int l=x-1,r=y+1; l=find_tree(l),r=find_tree(r); splay_tree(l,0); splay_tree(r,l); int pos=e[rot].ch[1]; pos=e[pos].ch[0]; e[pos].tag^=1; } void dfs(int now)//输出 { pushdown(now); if(e[now].ch[0]) dfs(e[now].ch[0]); if(e[now].v!=INF&&e[now].v!=-INF) printf("%d ",e[now].v); if(e[now].ch[1]) dfs(e[now].ch[1]); } void solve() { int n,m; scanf("%d%d",&n,&m); a[1]=-INF,a[n+2]=INF; for(int i=1;i<=n;i++) a[i+1]=i; rot=build_tree(1,n+2,0); while(m--) { int x,y; scanf("%d%d",&x,&y); reverse(x+1,y+1); } dfs(rot); }}S;int main(){ // ios::sync_with_stdio(false);// cin.tie(0); S.solve(); return 0;}/**/

转载地址:https://blog.csdn.net/DaNIelLAk/article/details/108282895 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:P4513 小白逛公园 线段树
下一篇:P2824 排序 线段树 + 二分

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月24日 18时52分18秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

linux优化deepin启动速度,如何让deepin启动更快? 2019-04-21
c语言读取多个连续的文件,C语言---多个线程读取文件 2019-04-21
cin gt gt a用c语言怎么写写,一初学者问我一问题,C语言的,然后我用笨拙的方法实现cin.putback... 2019-04-21
图片轮播c语言,IOS开发之UIScrollView实现图片轮播器的无限滚动 2019-04-21
c语言中操作数右移一位,Assembly C中的按位运算 2019-04-21
android 回收listview图片内存,用双缓存技术优化listview异步加载网络图片 2019-04-21
html中的em的使用方法,css布局的em的使用方法 2019-04-21
html画笛卡尔爱心,UG/NX 绘制一个爱心模型,你有几种方法能做出来呢? 2019-04-21
centos7重新加载服务的命令_squid代理服务器命中率的提高方法之一 2019-04-21
aps是什么意思_一文看懂ERP、APS和MES 2019-04-21
苹果地图副总裁_苹果发布 iOS 13 预览版,带来这些全新功能 2019-04-21
bert中的sep_在属性级情感分析中结合BERT和语法信息 2019-04-21
qlineedit文本改变时_word排版技巧:如何调整文本和页面的纵横显示 2019-04-21
李宏毅svm_李宏毅-深度学习 2019-04-21
php向mysql上传文件_PHP面向对象封装MySQL操作函数、文件上传 2019-04-21
asme标准最新版本_ASME的螺柱用什么标准 2019-04-21
jmeter录制手机客户端_米亚圆桌录制和回放观看功能全新上线 2019-04-21
hdfs orc格式_处理 HDFS 上的过多小文件的问题? 2019-04-21
缺失magisk正常工作所需的文件_总结了十个工作表看上去很凌乱的原因 2019-04-21
matlab将二值图像与原图重叠_MATLAB--数字图像处理 图像直方图规定化 2019-04-21