【bzoj1552/3506】[Cerc2007]robotic sort

Description

Input

输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。

Output

输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，（1 < = Pi < = N），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

 

题解：裸题

1 #include
       
          2 #include
        
           3 #include
         
            4 #include
          
             5 #include
           
              6   7 #define inf 1000000007  8 #define N 100007  9 #define ls c[p][0] 10 #define rs c[p][1] 11 using namespace std; 12 inline int read() 13 { 14     int x=0,f=1;char ch=getchar(); 15     while(ch>'9'||ch<'0'){
     if (ch=='-') f=-1;ch=getchar();} 16     while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} 17     return x*f; 18 } 19  20 int n,rt; 21 int a[N],rev[N],mi[N],flag[N],fa[N],sz[N],c[N][2],val[N],s[N]; 22  23 void update(int p) 24 { 25     sz[p]=sz[ls]+sz[rs]+1; 26     mi[p]=val[p],flag[p]=p; 27     if ((mi[ls]
            
             flag[ls])) mi[p]=mi[ls],flag[p]=flag[ls]; 28 if ((mi[rs]
             
              flag[rs])) mi[p]=mi[rs],flag[p]=flag[rs]; 29 } 30 void pushdown(int p) 31 { 32 if (rev[p]) 33 { 34 rev[p]^=1,rev[ls]^=1,rev[rs]^=1; 35 swap(c[p][0],c[p][1]); 36 } 37 } 38 void build(int l,int r,int f) 39 { 40 if (l>r) return; 41 if (l==r) 42 { 43 val[l]=a[l],sz[l]=1,fa[l]=f,mi[l]=a[l],flag[l]=l; 44 if (l
              
               >1; 49 build(l,mid-1,mid),build(mid+1,r,mid); 50 if (mid
               
                =num) return find(ls,num); 88 else if (sz[ls]+1==num) return p; 89 else return find(rs,num-sz[ls]-1); 90 } 91 int query(int l,int r) 92 { 93 int x=find(rt,l),y=find(rt,r+2); 94 splay(x,rt),splay(y,c[x][1]); 95 int now=c[y][0]; 96 return flag[now]; 97 } 98 void spin(int l,int r) 99 {100 int x=find(rt,l),y=find(rt,r+2);101 splay(x,rt),splay(y,c[x][1]);102 int now=c[c[x][1]][0];103 rev[now]^=1;104 }105 int main()106 {107 freopen("fzy.in","r",stdin);108 freopen("fzy.out","w",stdout);109 110 int n=read();111 for (int i=2;i<=n+1;i++)112 a[i]=read();113 a[1]=a[n+2]=a[0]=inf,mi[0]=inf;114 build(1,n+2,0),rt=(1+n+2)>>1;115 for (int i=1;i<=n;i++)116 {117 int wei=query(i,n);118 splay(wei,rt);119 if (i!=n) printf("%d ",sz[c[wei][0]]);120 else printf("%d",sz[c[wei][0]]);121 spin(i,sz[c[wei][0]]);122 }123 }