正文

[cqoi2014]排序机械臂

日拱一卒功不唐捐  日拱一卒功不唐捐  2022-08-23  689

关键词：

洛谷P3165 [CQOI2014]排序机械臂

https://www.luogu.org/problem/show?pid=3165

题目描述

为了把工厂中高低不等的物品按从低到高排好序，工程师发明了一种排序机械臂。它遵循一个简单的排序规则，第一次操作找到摄低的物品的位置P1,并把左起第一个至P1间的物品反序；第二次找到第二低的物品的位置P2,并把左起第二个至P2间的物品反序...最终所有的物品都会被排好序。

上图给出_个示例，第_次操作前，菝低的物品在位置4,于是把第1至4的物品反序；第二次操作前，第二低的物品在位罝6,于是把第2至6的物品反序...

你的任务便是编写一个程序，确定一个操作序列，即每次操作前第i低的物品所在位置Pi,以便机械臂工作。需要注意的是，如果有高度相同的物品，必须保证排序后它们的相对位置关系与初始时相同。

输入输出格式

输入格式：

第一行包含正整数n,表示需要排序的物品数星。

第二行包含n个空格分隔的整数ai,表示每个物品的高度。

输出格式：

输出一行包含n个空格分隔的整数Pi。

输入输出样例

输入样例#1：

6
3 4 5 1 6 2

输出样例#1：

4 6 4 5 6 6
基本框架:splay 区间反转+查询
流程：
1、数据排序 
   排序规则：高度小的在前，若高度相同，位置靠前的在前
2、建立平衡树，平衡树中直接存储物品的编号，即加上两个虚拟节点后，平衡树中的节点x，对应初始序列位置为x的点；平衡树的中序遍历，对应本次排序后的物品顺序
  物品的高度只在排序中有用，自建树开始高度完全没有用了
3、对于输出物品位置p，将物品旋转至根节点，输出左子树大小+1即可
4、区间反转
注意维护反转标记

#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
int n,fa[N],siz[N],ch[N][2],root,tag[N];
struct node
{
    int i,k;
}a[N];
inline bool cmp(node p,node q)
{
    if(p.k<q.k) return 1;
    if(p.k==q.k) return p.i<q.i;
    return 0;
}
inline void update(int k)
{
    siz[k]=siz[ch[k][0]]+siz[ch[k][1]]+1;
} 
inline void build(int l,int r,int f)
{
    if(l>r) return;
    int mid=l+r>>1;
    if(mid<f) ch[f][0]=mid;
    else ch[f][1]=mid;
    siz[mid]=1;fa[mid]=f;
    if(l==r) return;
    build(l,mid-1,mid);
    build(mid+1,r,mid);
    update(mid);
}
inline void down(int k)
{
    tag[k]^=1;
    if(ch[k][0]) tag[ch[k][0]]^=1;
    if(ch[k][1]) tag[ch[k][1]]^=1;
    swap(ch[k][0],ch[k][1]);
}
inline void rotate(int x,int & goal)
{
    int y=fa[x],z=fa[y],kind=ch[y][1]==x;
    if(y==goal) goal=x;
    else ch[z][ch[z][1]==y]=x;
    ch[y][kind]=ch[x][kind^1];ch[x][kind^1]=y;
    fa[y]=x;fa[x]=z;fa[ch[y][kind]]=y;
    update(y);
}
inline void splay(int x,int & goal)
{
    while(x!=goal)
    {
        int y=fa[x],z=fa[y];
        if(tag[z]) down(z);
            if(tag[y]) down(y);
                if(tag[x]) down(x);
        if(y!=goal)
        {
            if(ch[y][1]==x^ch[z][1]==y) rotate(x,goal);
            else rotate(y,goal);
        }
        rotate(x,goal);    
        update(x);
    }
} 
inline int find(int now,int k)
{
    if(tag[now]) down(now);
    int l=ch[now][0],r=ch[now][1];
    if(siz[l]+1==k) return now;
    if(k<=siz[l])  return find(l,k);
    return find(r,k-siz[l]-1);
}
inline void reverse(int l,int r)
{
    int x=find(root,l-1),y=find(root,r+1);
    splay(x,root);splay(y,ch[x][1]);
    tag[ch[y][0]]^=1;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {scanf("%d",&a[i+1].k); a[i+1].i=i+1;}
    a[1].i=1;a[n+2].i=n+2;a[n+2].k=2000000001;
    sort(a+1,a+n+3,cmp);
    build(1,n+2,0);root=n+3>>1;
    int p;
    for(int i=2;i<=n;i++)
    {
        splay(a[i].i,root);
        p=siz[ch[root][0]]+1;
        printf("%d ",p-1);
        reverse(i,p);
    }
    printf("%d",n);
}

3个错误：

①、标记下传

a.错误代码：

inline void down(int k)
{
tag[k]^=1;
tag[ch[k][0]]^=1;tag[ch[k][1]]^=1;
swap(ch[k][0],ch[k][1]);
}

错因：没有判断是否有左右孩子，如果没有孩子，为0，标记下穿至0号节点，在区间范围锁定时，如果l=1，查找0号节点，因为建树的时候，最初的父节点为0，所以就会误将0号节点的tag下传

b.splay中没有标记下传

if(tag[z]) down(z);
if(tag[y]) down(y);
if(tag[x]) down(x);

以前写的那个splay模板因为splay在find之后，而find标记下传了，所以splay不需要下传

②、排序

错误代码：

inline bool cmp(node p,node q)
{
return p.k<=q.k;
}

不能完成k相同时位置靠前的在前

③、查找位置

开始写了一个splay模板中的查找代码

错误代码：

inline int findpos(int now,int x)
{
if(x==now) return 1;
if(tag[now]) down(now);
if(x<now) return findpos(ch[now][0],x);
return siz[ch[now][0]]+1+findpos(ch[now][1],x);
}

错因：虽然一开始建立平衡树是按编号的大小顺序建立的，但建立后，区间的反转时平衡树的节点间没有大小关系，所以不能根据now和x的大小查找x

其实只要将x旋转至根节点，输出左子树大小+1即可

思维太死板、模式化

bzoj3506[cqoi2014]排序机械臂-splay(代码片段)

　　　　　　　　3506:[Cqoi2014]排序机械臂题目描述为了把工厂中高低不等的物品按从低到高排好序，工程师发明了一种排序机械臂。它遵循一个简单的排序规则，第一次操作找到高度最低的物品的位置 P_1P1? ，并把左起第... 查看详情

bzoj3506:[cqoi2014]排序机械臂

...中高低不等的物品按从低到高排好序，工程师发明了一种排序机械臂。它遵循一个简单的排序规则，第一次操作找到摄低的物品的位置P1,并把左起第一个至P1间的物品反序；第二次找到第二低的物品的位置P2,并把左起第二个至P2... 查看详情

libreoj2241-「cqoi2014」排序机械臂

PortalDescription给出一个$n(n\leq10^5)$个数的序列$\a_n\$，对该序列进行$n$次操作。若在第$i$次操作前第$i$小的数在$p_i$位置，则翻转区间$[i,p_i]$。易知$n$次操作后序列会变为升序。求出每一次的$p_i$。Solutionsplay。题里的\(... 查看详情

[cqoi2014]排序机械臂(代码片段)

嘟嘟嘟最近复习复习平衡树，然后又体会到了那种感觉：“写代码半小时，debug一下午”。这题其实就是让你搞一个数据结构，支持一下操作：1.区间翻转。2.查询区间最小值所在位置。刚开始我想错了，想直接维护点权最小的点... 查看详情

洛谷p3165[cqoi2014]排序机械臂

p3165[cqoi2014]排序机械臂(代码片段)

...中高低不等的物品按从低到高排好序，工程师发明了一种排序机械臂。它遵循一个简单的排序规则，第一次操作找到高度最低的物品的位置P1P_1P1?，并把左起第一个物品至P1P_1P1?间的物品(即区间[1,P1][1,P_1][1,P1?]间的物品)反序；第... 查看详情

洛谷p3165[cqoi2014]排序机械臂splay(代码片段)

...中高低不等的物品按从低到高排好序，工程师发明了一种排序机械臂。它遵循一个简单的排序规则，第一次操作找到高度最低的物品的位置$p_1$，并把左起第一个物品至$p_1$间的物品(即区间$[1,p_1]$间的物品)反序；第二次找到第二... 查看详情

1552&3506.[cqoi2014]排序机械臂平衡树-splay

DescriptionInput输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。Output输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，Pi表示第i次操作前第i... 查看详情

[bzoj1552][cerc2007]roboticsort&&[bzoj3506][cqoi2014]排序机械臂

非常垃圾的一道平衡树，结果被日了一天。很难受嗷嗷嗷首先不得不说网上的题解让我这个本来就不熟悉平衡树的彩笔很难受——并不好理解。还好Sinogi大佬非常的神，一眼就切掉了，而且用更加美妙的解法。题意在操作时，就... 查看详情

luogup3165[cqoi2014]排序机械臂(代码片段)

...和这题一起四倍经验的题：LuoguP4402[Cerc2007]roboticsort机械排序SP2059CERC07S-RoboticSortUVA1402RoboticSort这题作为一道十分经典的平衡树维护序列的问题，自然是值得一做的了。写完翻了下题解发现都是写Splay的dalao，少有的暴力FHQ_Treap党还... 查看详情

p3165[cqoi2014]排序机械臂（splay）(代码片段)

题意(n)个物品，依次排列，每个物品都有一个高度(hi)(n)次操作，第(i)次操作将区间[位置(i),第(i)低的物品(多个时取靠左的优先)的位置]翻转回答一个序列，第(i)个数表示每次操作前第(i)低的物品所在位置思路利用(splay)进行多次... 查看详情

[bzoj1552]排序机械臂

Splay大法是坠吼滴!1552:[Cerc2007]roboticsortTimeLimit:5Sec MemoryLimit:64MBSubmit:436 Solved:186[Submit][Status][Discuss]Description Input输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=1000 查看详情

bzoj3506排序机械臂（splay）

【BZOJ3506】排序机械臂（Splay）题面神TMBZOJ没有题面，感谢SYC的题面洛谷的题面也不错题解对于每次旋转的物体显然可以预处理出来现在只要模拟旋转操作就行了至于在哪里放标记的问题我只在第K大放会鬼。。所以在Splay里面也... 查看详情

bzoj-1552&3506roboticsort&排序机械臂splay

1552:[Cerc2007]roboticsortTimeLimit: 5Sec MemoryLimit: 64MBSubmit: 806 Solved: 329[Submit][Status][Discuss]DescriptionInput输入共两行，第一行为一个整数N，N表示物品的个数，1<=N< 查看详情

Kinect 机械臂检测

】Kinect机械臂检测【英文标题】：Kinectroboticarmdetection【发布时间】：2016-03-0111:56:18【问题描述】：我可以使用Kinect传感器检测机械臂(KUKALBRiiwa7R800)的运动并计算它的链接角度，以使其控制另一个机械臂。【问题讨论】：使用Kinec... 查看详情

ur机械臂+robotiqgripper+robotiqftsensor+gazebo+连接真实机械臂+网页控制

ur机械臂+robotiqgripper+robotiqftsensor+gazebo+连接真实机械臂+网页控制仓库地址：[ur_ws](https://github.com/borninfreedom/ur_ws)，欢迎debug和develop。xacro制作连接真实机械臂gazebo、moveit网页控制仓库... 查看详情

stm32控制机械臂抓取的代码

实现stm32控制机械臂抓取的代码，首先需要实现机械臂的控制程序，包括初始化、变量定义、初始位置、转矩计算等。其次，实现传感器的数据采集，例如光电传感器、避障传感器、力感传感器等。再者，根据传感器采集的数据... 查看详情

frankaemikapanda连接真实机械臂(代码片段)

FrankaEmikaPanda连接真实机械臂（二）虚拟环境下已经可以进行机械臂的拖动了，下一步就是PC连接机械臂，并通过plan控制机械臂运动。前文【FrankaEmikaPanda连接真实机械臂（一）】已经提到如何配置机械臂环... 查看详情