[bzoj1552\bzoj2506][Cqoi2014]robotic sort 排序机械臂_非旋转Treap

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

robotic sort 排序机械臂 bzoj-1552 bzoj-2506 Cqoi-2014

题目大意：给定一个序列，让你从1到n，每次将[1,p[i]]这段区间反转，p[i]表示整个物品权值第i小的。

注释：$1\le n\le 10^5$。

想法：非旋转Treap裸题，随题目要求。只需要非旋转Treap的最基本的函数和一个查询排名的函数即可。

最后，附上丑陋的代码... ...

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
#define mp make_pair
using namespace std;
typedef pair<int,int> par;
struct pig
{
int val,id,fin_val;
}t[N];
int n;
inline bool cmp1(pig x,pig y)
{
if(x.val!=y.val)return x.val<y.val;
return x.id<y.id;
}
inline bool cmp2(pig x,pig y)
{
return x.id<y.id;
}
struct Node
{
int ls,rs,size,key,fa;
bool turn;
}a[N];
int root;
inline void update(int x)
{
int ls=a[x].ls,rs=a[x].rs;
a[x].size=1;
if(ls)a[x].size+=a[ls].size;
if(rs)a[x].size+=a[rs].size;
}
inline void pushdown(int x)
{
if(a[x].turn)
{
swap(a[x].ls,a[x].rs);
if(a[x].ls)a[a[x].ls].turn^=1;
if(a[x].rs)a[a[x].rs].turn^=1;
a[x].turn=0;
}
}
int merge(int x,int y)
{
pushdown(x);pushdown(y);
if(!x||!y)return x|y;
if(a[x].key>a[y].key)
{
a[x].rs=merge(a[x].rs,y);
a[a[x].rs].fa=x;
update(x);
return x;
}
a[y].ls=merge(x,a[y].ls);
a[a[y].ls].fa=y;
update(y);
return y;
}
par split(int x,int k)
{
pushdown(x);
if(!k)return mp(0,x);
int ls=a[x].ls,rs=a[x].rs;
if(k==a[ls].size)
{
a[ls].fa=0;
a[x].ls=0;update(x);
return mp(ls,x);
}
if(k==a[ls].size+1)
{
a[rs].fa=0;
a[x].rs=0;update(x);
return mp(x,rs);
}
if(k<a[ls].size)
{
par t=split(ls,k);
a[t.first].fa=0,a[t.second].fa=x;
a[x].ls=t.second;
update(x);
return mp(t.first,x);
}
par t=split(rs,k-a[ls].size-1);
a[t.first].fa=x,a[t.second].fa=0;
a[x].rs=t.first;
update(x);
return mp(x,t.second);
}
int z[N],top;
int getrank(int x)
{
top=0;int t=x;
while(t)z[++top]=t,t=a[t].fa;
while(top)pushdown(z[top--]);
int ans=0,flag=1;
while(x)
{
if(flag)ans+=a[a[x].ls].size+1;
flag=(x==a[a[x].fa].rs);
x=a[x].fa;
}
return ans;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&t[i].val),t[i].id=i;
sort(t+1,t+n+1,cmp1);
for(int i=1;i<=n;i++)t[i].fin_val=i;
sort(t+1,t+n+1,cmp2);
for(int i=1;i<=n;i++)
{
int pos=t[i].fin_val;
a[pos].key=rand(),a[pos].size=1;
root=merge(root,pos);
}
for(int i=1;i<=n;i++)
{
int rank=getrank(i);
printf("%d",rank);
if(n-i)putchar(' ');
if(i==rank)continue;
par t2=split(root,rank),t1=split(t2.first,i-1);
a[t1.second].turn^=1;
root=merge(merge(t1.first,t1.second),t2.second);
}
return 0;
}