NC19933. [CQOI2014]排序机械臂
描述
上图给出一个示例，第一次操作前，最低的物品在位置4,于是把第1至4的物品反序；第二次操作前，第二低的物品在位罝6,于是把第2至6的物品反序...
你的任务便是编写一个程序，确定一个操作序列，即每次操作前第i低的物品所在位置Pi,以便机械臂工作。需要注意的是，如果有高度相同的物品，必须保证排序后它们的相对位置关系与初始时相同。
输入描述
第一行包含正整数n,表示需要排序的物品数星。
第二行包含n个空格分隔的整数ai,表示每个物品的高度。
输出描述
输出一行包含n个空格分隔的整数Pi。
示例1
输入:
6 3 4 5 1 6 2
输出:
4 6 4 5 6 6
C++14(g++5.4) 解法, 执行用时: 160ms, 内存消耗: 4324K, 提交时间: 2020-02-16 17:55:29
#include<bits/stdc++.h>
#define lson t[x].son[0]
#define rson t[x].son[1]
using namespace std;
const int MX=1e5+9;
const int inf=1e7+9;
struct node{
int fa,siz,res,val;
int son[2];
}t[MX*10];
int sz,root,n;
int top,rub[MX];
int siz(){
return top?rub[top--]:++sz;
}
int get(int x){
return t[t[x].fa].son[1]==x;
}
void update(int x){
t[x].siz=1;
if( lson )
t[x].siz+=t[lson].siz;
if( rson )
t[x].siz+=t[rson].siz;
}
void pushdown(int x){
if( t[x].res ){
swap(lson,rson);
if( lson )
t[lson].res^=1;
if( rson )
t[rson].res^=1;
t[x].res=0;
}
}
void rotate(int x){
int f=t[x].fa,ff=t[f].fa;
pushdown(f);
pushdown(x);
int kx=get(x),kf=get(f);
t[ff].son[kf]=x,t[x].fa=ff;
t[f].son[kx]=t[x].son[!kx],t[t[x].son[!kx]].fa=f;
t[x].son[!kx]=f,t[f].fa=x;
update(f);
update(x);
}
void splay(int rt,int x){
while( t[x].fa!=rt ){
int f=t[x].fa,ff=t[f].fa;
if( ff!=rt ){
if( get(x)==get(f) )
rotate(f);
else
rotate(x);
}
rotate(x);
}
if( rt==0 )
root=x;
}
int fin_siz(int k){
int x=root;
while( x ){
pushdown(x);
int temp=t[lson].siz;
if( k<=temp )
x=lson;
else if( k==temp+1 )
return x;
else{
k-=(temp+1);
x=rson;
}
}
}
void revers(int l,int r){
int x=fin_siz(l),y=fin_siz(r);
//printf("l:%d r:%d x:%d y:%d\n",l,r,x,y);
splay(0,x);
splay(x,y);
t[t[y].son[0]].res^=1;
}
struct Node{
int num,id;
bool operator<(const Node&a)const{
if( num!=a.num )
return num<a.num;
else
return id<a.id;
}
}a[MX];
int build(int l,int r,int fa){
if( l>r )
return 0;
int mid=(l+r)>>1;
t[mid].fa=fa;
t[mid].siz=1;
t[mid].val=a[mid].num;
t[mid].res=0;
t[mid].son[0]=build(l,mid-1,mid);
t[mid].son[1]=build(mid+1,r,mid);
update(mid);
return mid;
}
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d",&n);
a[1].num=-inf,a[1].id=1;
for( int i=2 ; i<=n+1 ; i++ ){
scanf("%d",&a[i].num);
a[i].id=i;
}
a[n+2].num=inf,a[n+2].id=n+2;
root=build(1,n+2,0);
sort(a+1,a+3+n);
for( int i=2 ; i<=n+1 ; i++ ){
int x=a[i].id;
splay(0,x);
//printf("i:%d\n",i);
printf("%d ",t[lson].siz);
revers(i-1,t[lson].siz+2);
}
return 0;
}
C++ 解法, 执行用时: 123ms, 内存消耗: 3832K, 提交时间: 2021-09-18 11:46:08
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define N 100005
using namespace std;
struct note{int v,w;}a[N];
bool cmp(note x,note y) {return x.v<y.v||x.v==y.v&&x.w<y.w;}
int n,t[N][2],f[N],size[N],rev[N],d[N],ans[N],root;
void updata(int x) {
size[x]=size[t[x][0]]+size[t[x][1]]+1;
}
int son(int x) {
if (x==t[f[x]][0]) return 0;else return 1;
}
void back(int x) {
rev[x]^=1;swap(t[x][0],t[x][1]);
}
void down(int x) {
if (rev[x]) {
if (t[x][0]) back(t[x][0]);
if (t[x][1]) back(t[x][1]);
rev[x]=0;
}
}
void remove(int x,int y) {
if (x==y) return;
do {
d[++d[0]]=x;x=f[x];
} while (x!=y);
while (d[0]) down(d[d[0]--]);
}
void rotate(int x) {
int y=f[x],z=son(x);f[x]=f[y];
if (f[y]) t[f[y]][son(y)]=x;
t[y][z]=t[x][1-z];
if (t[x][1-z]) f[t[x][1-z]]=y;
t[x][1-z]=y;f[y]=x;
updata(y);updata(x);
}
void splay(int x,int y) {
remove(x,y);
while (f[x]!=y) {
if (f[f[x]]!=y)
if (son(x)==son(f[x])) rotate(f[x]);
else rotate(x);
rotate(x);
}
if (!y) root=x;
}
int build(int l,int r,int fa) {
if (l>r) return 0;
int m=(l+r)/2;
f[m]=fa;size[m]=r-l+1;
if(l==r)return l;
t[m][0]=build(l,m-1,m);
t[m][1]=build(m+1,r,m);
return m;
}
void find(int x) {
down(x);x=t[x][1];
while (x) {
down(x);
if (t[x][0]) x=t[x][0];
else break;
}
splay(x,0);
}
void del(int x) {
f[t[x][0]]=f[x];
t[f[x]][0]=t[x][0];
updata(f[x]);
}
int main() {
scanf("%d",&n);
fo(i,1,n) scanf("%d",&a[i].v),a[i].w=i;
build(1,n+1,0);
sort(a+1,a+n+1,cmp);
fo(i,1,n) {
splay(a[i].w,0);back(t[root][0]);
printf("%d",size[t[root][0]]+i);
if (i!=n) printf(" ");
find(root);del(t[root][0]);
}
}