BZOJ1861 [Zjoi2006]Book 书架_weixin_30505225的博客-程序员宝宝

Splay维护操作。

学习了一个很好的remove操作。

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 const int N=8e4+5;
  4 const int inf=1e9;
  5 int fa[N],c[N][2],size[N],pos[N],a[N],v[N],n,m,rt;
  6 void update(int x)
  7 {
  8     size[x]=size[c[x][0]]+size[c[x][1]]+1;
  9 }
 10 void rotate(int x,int &k)
 11 {
 12     int y=fa[x],z=fa[y];
 13     int l=(c[y][1]==x);int r=l^1;
 14     if(y==k)k=x;else c[z][c[z][1]==y]=x;
 15     fa[x]=z;fa[y]=x;fa[c[x][r]]=y;
 16     c[y][l]=c[x][r];c[x][r]=y;
 17     update(y);update(x);
 18 }
 19 void splay(int x,int &k)
 20 {
 21     while(x!=k)
 22     {
 23         int y=fa[x],z=fa[y];
 24         if(y!=k)
 25         {
 26             if(x==c[y][0]^y==c[z][0])rotate(x,k);
 27             else rotate(y,k);
 28         }
 29         rotate(x,k);
 30     }
 31 }
 32 int find(int x,int k)
 33 {
 34     if(size[c[x][0]]+1==k)return x;
 35     else if(size[c[x][0]]>=k)return find(c[x][0],k);
 36     else return find(c[x][1],k-size[c[x][0]]-1);
 37 }
 38 void del(int k)
 39 {
 40     int x=find(rt,k-1);int y=find(rt,k+1);
 41     splay(x,rt);splay(y,c[x][1]);
 42     int z=c[y][0];c[y][0]=0;fa[z]=size[z]=0;
 43     update(y);update(x);
 44 }
 45 void remove(int q,int w)
 46 {
 47     int k=pos[q],rank,x,y;
 48     
 49     splay(k,rt);rank=size[c[rt][0]]+1;
 50     del(rank);
 51     if(w==inf)x=find(rt,n),y=find(rt,n+1);
 52     else if(w==-inf)x=find(rt,1),y=find(rt,2);
 53     else x=find(rt,rank+w-1),y=find(rt,rank+w);
 54     splay(x,rt);splay(y,c[x][1]);
 55     size[k]=1;fa[k]=y;c[y][0]=k;
 56     update(y);update(x);
 57 }
 58 void build(int l,int r,int f)
 59 {
 60     if(l>r)return;
 61     int mid=l+r>>1;
 62     fa[mid]=f;c[f][mid>=f]=mid;v[mid]=a[mid];
 63     if(l==r)
 64     {
 65         size[l]=1;return;
 66     }
 67     build(l,mid-1,mid);build(mid+1,r,mid);
 68     update(mid);
 69     return;
 70 }
 71 int main()
 72 {
 73     scanf("%d%d",&n,&m);
 74     for(int i=2;i<=n+1;++i)
 75     {
 76         scanf("%d",&a[i]);pos[a[i]]=i;
 77     }
 78     build(1,n+2,0);rt=(n+3)>>1;char s[10];int k,ss,t;
 79     for(int i=1;i<=m;++i)
 80     {
 81         scanf("%s",s);
 82         if(s[0]=='Q')
 83         {
 84             scanf("%d",&k);
 85             printf("%d\n",v[find(rt,k+1)]);
 86         }
 87         else if(s[0]=='T')
 88         {
 89             scanf("%d",&k);
 90             remove(k,-inf);
 91         }
 92         else if(s[0]=='B')
 93         {
 94             scanf("%d",&k);
 95             remove(k,inf);
 96         }
 97         else if(s[0]=='I')
 98         {
 99             scanf("%d%d",&ss,&t);remove(ss,t);
100         }
101         else
102         {
103             scanf("%d",&k);k=pos[k];
104             splay(k,rt);
105             printf("%d\n",size[c[rt][0]]-1);
106         }
107     }
108     return 0;
109 }
 

 

转载于:https://www.cnblogs.com/nbwzyzngyl/p/8289667.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30505225/article/details/99431524

智能推荐

中兴U880 完美版2.3.7第三弹炫目登场,你还在为刷机而烦恼?来吧!它值得你拥有!!!!_打杂人的博客-程序员宝宝

本帖最后由 销魂的猫 于 2012-1-30 14:10 编辑http://wenku.baidu.com/view/d0e4d9350b4c2e3f572763fb.html下个版本需等本帖达到1000个评分、5000个回复后再发布!免得有那么多的伸手党!   完美版第四弹热点功能抢先报:1、装逼专用4.0.1版本,2、提升软件运行速度3、系统设置背景改为 图

使用Flink Watermark sideOutputLateData的坑_ooobenooo的博客-程序员宝宝

Flink Watermark是用于处理数据乱序问题,网上已经有很多优秀的文章介绍,这里就不重复了。参考:https://ci.apache.org/projects/flink/flink-docs-release-1.10/dev/event_timestamps_watermarks.html今天要说的使用Watermark过程中自己挖的坑,使用sideOutputLateData()过程中没有正常输出的问题,在此记录一下:先来看一下源码解析:/** * Send late ar

Protocol Buffers for Object-C_凯哥的世界你不懂的博客-程序员宝宝

一、先点击链接去了解一下,或者 google一下http://code.google.com/intl/zh-CN/apis/protocolbuffers/二、protobuf的使用1、编译Protocol Buffers  A.下载Protocol Buffers将下载解压后的文件存放至Applications目录下,进到ProtocolBuffers-2.2.

python 开发模块之Requests-multipart/form-data_luo2424348224的博客-程序员宝宝

      HTTP 协议规定 POST 提交的数据必须放在消息主体(entity-body)中,但协议并没有规定数据必须使用什么编码方式。常见的有四种编码方式,今天就做下multipart/form-data第二种常见编码方式。       第一种常见的已经发布了:http://blog.csdn.net/luo2424348224/article/details/79637524   这又是一...

PAT 1086 就不告诉你(15 分)- 乙级_柳婼的博客-程序员宝宝

做作业的时候,邻座的小盆友问你:“五乘以七等于多少?”你应该不失礼貌地围笑着告诉他:“五十三。”本题就要求你,对任何一对给定的正整数,倒着输出它们的乘积。输入格式:输入在第一行给出两个不超过 1000 的正整数 A 和 B,其间以空格分隔。输出格式:在一行中倒着输出 A 和 B 的乘积。输入样例:5 7输出样例:53分析:a 和 b的乘积转换成字符串,再将字符串反转,最后将反转过的...

线性代数【四】:向量(1):线性相关及其判别,极大线性无关组,等价向量组_不会算命的赵半仙的博客-程序员宝宝_如何判断极大线性无关组

本节为线性代数复习笔记的第二部分,矩阵的概念与计算(1),主要包括:行列式的几何意义,行列式的展开计算(余子式,代数余子式),行列式的性质,特殊的五个行列式以及克拉默法则。1.欢迎扫描二维码关注微信公众号 深度学习与数学   [每天获取免费的大数据、AI等相关的学习资源、经典和最新的深度学习相关的论文研读,算法和其他互联网技能的学习,概率论、线性代数等高等数学知识的回顾]...

随便推点

(原创)咱们公司遇到一个想开发和抖音一样的app的客户?_qq18723817197的博客-程序员宝宝

如果客户说想开发一款和抖音一模一样的app,结果会?——链环科技

我和你们不同--和谐就是和而不同--就是多样性的统一_LLKJDLLKJD的博客-程序员宝宝

     软件开发我从来没有研究过,我是寻求一个帮助偶然来到这个空间,希望哪位朋友能够帮助我编写一个这样简单的软件---将标志某商品的品名、产地生产商、经销商、规格型号、产品编号、特殊字符的信息编写成为另外一组可以自由设定的信息,当输入其中某一段信息后,就可以自动导出这些自由设定的信息,就好象户口管理,输入名字,就可以导出身份证号码一样;用途是:好查找库房放置的商品位置。    我的手机号码是

每个程序员都必须遵守的编程原则_马兆娟的博客-程序员宝宝

恰巧看到这篇文章,学过面向对象语言的人会很容易理解里面涉及的编程原则,这些原则恰恰是面向对象语言中常说的。感觉这篇文章写得不错,共享出来,共同学习……原文地址:http://www.aqee.net/principles-of-good-programming/      ============================分割线,请看下文=====================

数据处理平台架构中的SMACK组合:Spark、Mesos、Akka、Cassandra以及Kafka_似水流年的博客-程序员宝宝

摘要: 在今天的文章中,我们将着重探讨如何利用SMACK(即Spark、Mesos、Akka、Cassandra以及Kafka)堆栈构建可扩展数据处理平台。虽然这套堆栈仅由数个简单部分组成,但其能够实现大量不同系统设计。除了纯粹的批量或者流处理机制之外,我们亦可借此实现复杂的Lambda以及Kappa架构。在今天的文章中,我们将着重探讨如何利用SMACK(即Spark、Mesos、Akka、Cassandra以及Kafka)堆栈构建可扩展数据处理平台。虽然这套堆栈仅由数个简单部分组成,但其能够实现大量不

HashSet和HashMap的区别比较_ccxuxuxu的博客-程序员宝宝

HashSet 实现的Set接口,集合中不允许出现重复的值(如果重复会覆盖):package com.wlf.base;public class Person{ public Person(String name, int age) { this.name = name; this.age = age; }