1552/3506. [CQOI2014]排序机械臂【平衡树-splay】

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翻转区间即可。

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #define N (100000+100)
  6 using namespace std;
  7 struct node
  8 {
  9     int id,num;
 10 } b[N];
 11 int Key[N],Rev[N],Size[N];
 12 int Father[N],Son[N][2];
 13 int n,Root,a[N],Rank[N];
 14 
 15 bool cmp(node a,node b)
 16 {
 17     return a.num==b.num?a.id<b.id:a.num<b.num;
 18 }
 19 inline int Get(int x)
 20 {
 21     return Son[Father[x]][1]==x;
 22 }
 23 
 24 inline void Update(int x)
 25 {
 26     Size[x]=Size[Son[x][0]]+Size[Son[x][1]]+1;
 27 }
 28 
 29 inline void Pushdown(int x)
 30 {
 31     if (Rev[x])
 32     {
 33         Rev[x]=0;
 34         swap(Son[x][0],Son[x][1]);
 35         Rev[Son[x][0]]^=1;
 36         Rev[Son[x][1]]^=1;    
 37     }
 38 }
 39 
 40 inline void Rotate(int x)
 41 {
 42     Pushdown(Father[x]);
 43     Pushdown(x);
 44     int wh=Get(x);
 45     int fa=Father[x],fafa=Father[fa];
 46     Son[fa][wh]=Son[x][wh^1];
 47     Father[fa]=x;
 48     if (Son[fa][wh]) Father[Son[fa][wh]]=fa;
 49     Son[x][wh^1]=fa;
 50     Father[x]=fafa;
 51     if (fafa) Son[fafa][Son[fafa][1]==fa]=x;
 52     Update(fa);
 53     Update(x);
 54 }
 55 
 56 inline void Splay(int x,int tar)
 57 {
 58     for (int fa;(fa=Father[x])!=tar;Rotate(x))
 59         if (Father[fa]!=tar)
 60             Rotate(Get(fa)==Get(x)?fa:x);
 61     if (!tar) Root=x;
 62 }
 63 
 64 void Build(int l,int r,int fa)
 65 {
 66     if (l>r) return;
 67     if (l==r)
 68     {
 69         Size[l]=1;
 70         Father[l]=fa;
 71         Son[fa][l>fa]=l;
 72         return;
 73     }
 74     int mid=(l+r)>>1;
 75     Build(l,mid-1,mid);
 76     Build(mid+1,r,mid);
 77     Father[mid]=fa;
 78     Son[fa][mid>fa]=mid;
 79     Update(mid);
 80 }
 81 
 82 int Findx(int x)
 83 {
 84     int now=Root;
 85     while (1)
 86     {
 87         Pushdown(now);
 88         if (Size[Son[now][0]]>=x)
 89             now=Son[now][0];
 90         else
 91         {
 92             x-=Size[Son[now][0]];
 93             if (x==1)
 94             {
 95                 Splay(now,0);
 96                 return now;
 97             }
 98             x--;
 99             now=Son[now][1];
100         }
101     }
102 }
103 
104 inline int Split(int x,int y)
105 {
106     int xx=Findx(x),yy=Findx(y);
107     Splay(xx,0);
108     Splay(yy,xx);
109     return Son[yy][0];
110 }
111 
112 int main()
113 {
114     scanf("%d",&n);
115     for (int i=1; i<=n; ++i)
116     {
117         scanf("%d",&a[i+1]);
118         b[i].id=i+1;
119         b[i].num=a[i+1];
120     }
121     sort(b+1,b+n+1,cmp);
122     for (int i=1; i<=n; ++i)
123         Rank[i]=b[i].id;
124     Build(1,n+2,0);
125     Root=(n+3)/2;
126     for (int i=1; i<=n; ++i)
127     {
128         Splay(Rank[i],0);
129         int ans=Size[Son[Root][0]]+1;
130         printf("%d ",ans-1);
131         int hh=Split(i,ans+1);
132         Rev[hh]^=1;
133     }
134 }