bzoj 1552: [Cerc2007]robotic sort && bzoj 3506: [Cqoi2014]排序机械臂（splay区间翻转）

1552: [Cerc2007]robotic sort

Time Limit: 5 Sec   Memory Limit: 64 MB
Submit: 1206   Solved: 460
[ Submit][ Status][ Discuss]

Description

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准没错了

数字可能重复所以要离散化，因为相同数字在前面的先翻转，所以可以直接重新标号

pos[i]记录第i小的数所在树的节点编号，每次查询第i小的物品位置只要将对应的节点翻转到根

左子树的个数+1（因为开了两个哨兵节点所以这里就是左子树的个数）就是当前序列的位置

输出答案之后翻转区间，和http://blog.csdn.net/jaihk662/article/details/75675443一模一样

注意延迟标记要在"splay"的时候从根往下放！

比如要将节点x旋到根，那么从根到x这一路全部需要更新，并且更新顺序一定是从根到x

#include<stdio.h>
#include<algorithm>
using namespace std;
typedef struct Res
{
int val;
int id;
bool operator < (const Res &b) const
{
if(id<b.id)
return 1;
return 0;
}
}Res;
Res s[100005];
bool comp(Res a, Res b)
{
if(a.val<b.val || a.val==b.val && a.id<b.id)
return 1;
return 0;
}
int n, m, root;
int fa[100005], tre[100005][2], v[100005], siz[100005], rev[100005], temp[100005], pos[100005];
void Update(int k)
{
siz[k] = siz[tre[k][0]]+siz[tre[k][1]]+1;
}
void Create(int l, int r, int last)
{
int mid;
if(l>r)
return;
mid = (l+r)/2;
if(l==r)
{
fa[mid] = last;
siz[mid] = 1;
if(mid<last)  tre[last][0] = mid;
else  tre[last][1] = mid;
return;
}
Create(l, mid-1, mid);
Create(mid+1, r, mid);
fa[mid] = last;
if(mid<last)  tre[last][0] = mid;
else  tre[last][1] = mid;
Update(mid);
}
void Lazy(int k)
{
if(rev[k])
{
swap(tre[k][0], tre[k][1]);
rev[tre[k][0]] ^= 1;
rev[tre[k][1]] ^= 1;
rev[k] = 0;
}
}
void Rotate(int x, int &k)
{
int l, r, y, z;
y = fa[x], z = fa[y];
if(tre[y][0]==x)  l = 0;
else  l = 1;
r = l^1;
if(y==k)
k = x;
else
{
if(tre[z][0]==y)  tre[z][0] = x;
else  tre[z][1] = x;
}
fa[x] = z, fa[y] = x;
fa[tre[x][r]] = y;
tre[y][l] = tre[x][r];
tre[x][r] = y;
Update(y);
Update(x);
}
void Splay(int x, int &k)
{
int i, y, z, cnt = 0;
for(i=x;fa[i];i=fa[i])
temp[++cnt] = i;
for(i=cnt;i>=1;i--)
Lazy(temp[i]);
while(x!=k)
{
y = fa[x], z = fa[y];
if(y!=k)
{
if((tre[y][0]==x)^(tre[z][0]==y))
Rotate(x, k);
else
Rotate(y, k);
}
Rotate(x, k);
}
}
int Find(int k, int rank)
{
int l, r;
Lazy(k);
l = tre[k][0], r = tre[k][1];
if(siz[l]+1==rank)
return k;
else if(siz[l]>=rank)
return Find(l, rank);
else
return Find(r, rank-siz[l]-1);
}
void Turn(int l, int r)
{
int x, y, z;
x = Find(root, l-1);
y = Find(root, r+1);
Splay(x, root);
Splay(y, tre[x][1]);
z = tre[y][0];
rev[z] ^= 1;
}
int main(void)
{
int n, i, ans;
scanf("%d", &n);
for(i=1;i<=n;i++)
{
scanf("%d", &s[i].val);
s[i].id = i;
}
sort(s+1, s+n+1, comp);
for(i=1;i<=n;i++)
s[i].val = i;
sort(s+1, s+n+1);
for(i=2;i<=n+1;i++)
{
v[i] = s[i-1].val;
pos[v[i]] = i;
}
Create(1, n+2, 0);
root = (n+3)/2;
for(i=1;i<=n;i++)
{
Splay(pos[i], root);
ans = siz[tre[pos[i]][0]];
if(i!=1)
printf(" ");
printf("%d", ans);
Turn(i+1, ans+1);
}
printf("\n");
return 0;
}