【BZOJ1552】[Cerc2007]robotic sort Splay

时间:2021-03-18 23:50:45

【BZOJ1552】[Cerc2007]robotic sort

Description

【BZOJ1552】[Cerc2007]robotic sort Splay

Input

输入共两行,第一行为一个整数N,N表示物品的个数,1<=N<=100000。第二行为N个用空格隔开的正整数,表示N个物品最初排列的编号。

Output

输出共一行,N个用空格隔开的正整数P1,P2,P3…Pn,Pi表示第i次操作前第i小的物品所在的位置。 注意:如果第i次操作前,第i小的物品己经在正确的位置Pi上,我们将区间[Pi,Pi]反转(单个物品)。

Sample Input

6
3 4 5 1 6 2

Sample Output

4 6 4 5 6 6

题解:继续复习Splay,本题问的是编号第i小的位置,那我们就直接先将编号排序,用排名来充当该物品新的编号,并用新编号建一个Splay,那么我们在查询的时候就只需要知道新编号为i的点在Splay中的位置就行了。然后区间反转什么的就简单了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=100010;
struct node
{
int ch[2],fa,size,tag;
}p[maxn];
struct item
{
int num,org;
}it[maxn];
int n,root,v[maxn];
bool cmp(item a,item b)
{
if(a.num==b.num) return a.org<b.org;
return a.num<b.num;
}
int readin()
{
int ret=0; char gc;
while(gc<'0'||gc>'9') gc=getchar();
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret;
}
void pushup(int x)
{
p[x].size=p[p[x].ch[0]].size+p[p[x].ch[1]].size+1;
}
void pushdown(int x)
{
if(p[x].tag)
{
swap(p[x].ch[0],p[x].ch[1]);
if(p[x].ch[0]) p[p[x].ch[0]].tag^=1;
if(p[x].ch[1]) p[p[x].ch[1]].tag^=1;
p[x].tag=0;
}
}
void rotate(int x,int &k)
{
int y=p[x].fa,z=p[y].fa,d=(x==p[y].ch[1]);
if(y==k) k=x;
else p[z].ch[y==p[z].ch[1]]=x;
p[x].fa=z,p[y].fa=x,p[y].ch[d]=p[x].ch[d^1];
if(p[x].ch[d^1]) p[p[x].ch[d^1]].fa=y;
p[x].ch[d^1]=y;
pushup(y),pushup(x);
}
void build(int l,int r,int last)
{
if(l>r) return ;
int mid=l+r>>1;
if(last) p[v[last]].ch[mid>last]=v[mid];
p[v[mid]].fa=v[last];
build(l,mid-1,mid),build(mid+1,r,mid);
pushup(v[mid]);
}
int find(int x,int y)
{
pushdown(x);
if(y==p[p[x].ch[0]].size+1) return x;
if(y<=p[p[x].ch[0]].size) return find(p[x].ch[0],y);
else return find(p[x].ch[1],y-p[p[x].ch[0]].size-1);
}
int qrank(int x)
{
if(x==root) return p[p[x].ch[0]].size+1;
int ret=qrank(p[x].fa);
pushdown(x);
if(x==p[p[x].fa].ch[0]) ret-=p[p[x].ch[1]].size+1;
else ret+=p[p[x].ch[0]].size+1;
return ret;
}
void splay(int x,int &k)
{
while(x!=k)
{
int y=p[x].fa,z=p[y].fa;
if(y!=k)
{
if((x==p[y].ch[0])^(y==p[z].ch[0])) rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int main()
{
scanf("%d",&n);
int i;
for(i=1;i<=n;i++) it[i].num=readin(),it[i].org=i;
sort(it+1,it+n+1,cmp);
for(i=1;i<=n;i++) v[it[i].org+1]=i;
v[1]=n+1,v[n+2]=n+2;
root=v[(n+3)>>1];
build(1,n+2,0);
for(i=1;i<n;i++)
{
int temp=qrank(i);
printf("%d ",temp-1);
splay(find(root,i),root);
splay(find(root,temp+1),p[root].ch[1]);
p[p[p[root].ch[1]].ch[0]].tag^=1;
}
printf("%d",n);
return 0;
}

【BZOJ1552】[Cerc2007]robotic sort Splay的更多相关文章

  1. 【bzoj1552】&lbrack;Cerc2007&rsqb;robotic sort

    题目描述 输入 输入共两行,第一行为一个整数N,N表示物品的个数,1<=N<=100000.第二行为N个用空格隔开的正整数,表示N个物品最初排列的编号. 输出 输出共一行,N个用空格隔开的 ...

  2. 【bzoj1552&sol;3506】&lbrack;Cerc2007&rsqb;robotic sort splay翻转,区间最值

    [bzoj1552/3506][Cerc2007]robotic sort Description Input 输入共两行,第一行为一个整数N,N表示物品的个数,1<=N<=100000. ...

  3. BZOJ 1552&colon; &lbrack;Cerc2007&rsqb;robotic sort&lpar; splay &rpar;

    kpm大神说可以用块状链表写...但是我不会...写了个splay.... 先离散化 , 然后splay结点加个min维护最小值 , 就可以了... ( ps BZOJ 3506 题意一样 , 双倍经 ...

  4. 洛谷 P4402 BZOJ1552 &sol; 3506 &lbrack;Cerc2007&rsqb;robotic sort 机械排序

    FHQ_Treap 太神辣 蒟蒻初学FHQ_Treap,于是来到了这道略显板子的题目 因为Treap既满足BST的性质,又满足Heap的性质,所以,对于这道题目,我们可以将以往随机出的额外权值转化为每 ...

  5. &lbrack;BZOJ1552&rsqb; &lbrack;Cerc2007&rsqb; robotic sort &lpar;splay&rpar;

    Description Input 输入共两行,第一行为一个整数N,N表示物品的个数,1<=N<=100000.第二行为N个用空格隔开的正整数,表示N个物品最初排列的编号. Output ...

  6. 【HDOJ】1890 Robotic Sort

    伸展树伤不起啊,很容易wa,很容易T,很容易M. /* 1890 */ #include <iostream> #include <string> #include <m ...

  7. BZOJ1552&sol;3506 &lbrack;Cerc2007&rsqb;robotic sort

    Splay 与之前不同的是如果你仅仅是翻转左右区间的话可以在find里面做因为对他有影响的子树在做之前一定在他的上面从上到下搜索的过程可以把rever做了. 但这道题要求我们输出转换之前的,因此不能保 ...

  8. &lbrack;BZOJ1552&rsqb;&lbrack;Cerc2007&rsqb;robotic sort

    [BZOJ1552][Cerc2007]robotic sort 试题描述 输入 输入共两行,第一行为一个整数N,N表示物品的个数,1<=N<=100000.第二行为N个用空格隔开的正整数 ...

  9. bzoj 1552&colon; &lbrack;Cerc2007&rsqb;robotic sort

    1552: [Cerc2007]robotic sort Time Limit: 5 Sec  Memory Limit: 64 MBSubmit: 1198  Solved: 457[Submit] ...

随机推荐

  1. Saltstack

    一.Satlstack的概述 Saltstack是什么? Salt是一种和以往不同的基础设施管理方法,它是建立在大规模系统高速通讯能力可以大幅提升的想法上.这种方法使得Salt成为一个强大的能够解决基 ...

  2. sqlite与多线程

    数据库支持三种线程模式 Single-thread. In this mode, all mutexes are disabled and SQLite is unsafe to use in mor ...

  3. JavaWeb学习记录(六)——用户登录功能之Session与验证码验证功能的实现

    一.产生验证码的工具类 package blank.util; import java.awt.Color;import java.awt.Graphics;import java.awt.image ...

  4. java工具类系列 (四&period;SerializationUtils)

    java工具类系列 (四.SerializationUtils) SerializationUtils该类为序列化工具类,也是lang包下的工具,主要用于序列化操作 import java.io.Se ...

  5. ZigBee HomeAutomation分析

    引用请注明出处!联系邮箱是huhao0126@163.com 本例程讲解,基于TI CC2530-2.5.1a中的HomeAutomation文件夹中的SampleLight和SampleSwitch ...

  6. mvc日期控件datepick的几篇文章,日后再总结吧

    instinctcoder里有两篇,入门级的 http://instinctcoder.com/asp-net-mvc-4-jquery-datepicker/ http://instinctcode ...

  7. js跨域问题解决方案

     跨域:当协议.域名.端口号任何一个不相同时,叫称为跨域.   HTML5  CORS(cross-origin-resource-sharing)跨域资源共享: 原理:当需要访问跨域的资源时,可以通 ...

  8. 手机网页制作教程META标签你知道多少?【转&plus;加】

    一.天猫 <title>天猫触屏版</title> <meta content="text/html; charset=utf-8" http-equ ...

  9. 使用Nexus2搭建Maven本地仓库

    由于OS为WindowsXP,而Nexus3forWindows为x64版本,只能选择安装nexus2了. Windows(x86)平台,Nexus Repository Manager OSS 2. ...

  10. 算法提高 P0102

    用户输入三个字符,每个字符取值范围是0-9,A-F.然后程序会把这三个字符转化为相应的十六进制整数,并分别以十六进制,十进制,八进制输出,十六进制表示成3位,八进制表示成4位,若不够前面补0.(不考虑 ...