Robotic Sort

题意：给一个数列，用某一特定的方法对其进行排序。其排序方法是，第i次排序时，找到第i小的元素的位置p，输出这个p，并将[i,p]这段区间翻转。进行n次这样的操作后，序列有序。解题思路：以前用splay写过，思路是抄的别人的。学习treap后，重新再想了一下这个题，想到了一种新的思路。大概是这样的：首先，离散化还是有必要的，因为它会根据原序列里的位置定下其元素的大小。然后对于每次这样的操作，我们要找的必然是最小的那个元素。所以，我们要只需要维护区间的最小值，以及一个翻转标记。那么，我们如何寻找答案呢？显然，我们只要走最小值的值为i的那颗子树就好了，而且必然是能找到的。这样还有一个优点是，我们不需要像以前那种做法那样，从事先记录好的id往上走一遍了，因为我们往下走的时候，会把翻转标记都往下更新，这样，每次我们到达的节点，其信息必然是正确的，而且其子树的最小值信息也是正确的，那么我们就能根据这个最小值信息寻找相应的子树了。代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
      #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
            
              #define lowbit(x) (x&(-x)) #define ll __int64 #define lson l , m , rt << 1 #define rson m + 1 , r , rt << 1 | 1 #define new_edge(a,b,c) edge[tot].t = b , edge[tot].v = c , edge[tot].next = head[a] , head[a] = tot ++ using namespace std; const int maxn = 211111 ; int num[maxn] , pos[maxn] ; int cmp ( int i , int j ) { if ( num[i] == num[j] ) return i < j ; return num[i] < num[j] ; } struct Treap { int c[2][maxn] , size[maxn] , p[maxn] ; int val[maxn] , mi[maxn] ; int col[maxn] ; int tot ; int new_node ( int v ) { size[++tot] = 1 ; p[tot] = rand () ; c[0][tot] = c[1][tot] = col[tot] = 0 ; mi[tot] = val[tot] = v ; return tot ; } int build ( int l , int r ) { if ( l > r ) return 0 ; int mid = l + r >> 1 ; int temp = new_node ( num[mid] ) ; c[0][temp] = build ( l , mid - 1 ) ; c[1][temp] = build ( mid + 1 , r ) ; push_up ( temp ) ; return temp ; } void color ( int rt ) { if ( !rt ) return ; col[rt] ^= 1 ; swap ( c[0][rt] , c[1][rt] ) ; } void push_down ( int rt ) { if ( col[rt] ) { color ( c[0][rt] ) ; color ( c[1][rt] ) ; col[rt] = 0 ; } } void push_up ( int rt ) { int ls = c[0][rt] , rs = c[1][rt] ; size[rt] = size[ls] + size[rs] + 1 ; mi[rt] = min ( val[rt] , min ( mi[ls] , mi[rs] ) ) ; } int merge ( int x , int y ) { if ( !x ) return y ; if ( !y ) return x ; push_down ( x ) ; push_down ( y ) ; if ( p[x] < p[y] ) { c[1][x] = merge ( c[1][x] , y ) ; push_up ( x ) ; return x ; } c[0][y] = merge ( x , c[0][y] ) ; push_up ( y ) ; return y ; } void split ( int rt , int &x , int &y , int k ) { push_down ( rt ) ; int ls = c[0][rt] , rs = c[1][rt] ; if ( val[rt] == k ) { x = rt , y = c[1][rt] ; c[1][rt] = 0 ; push_up ( rt ) ; return ; } if ( mi[ls] == k ) { split ( ls , x , y , k ) ; c[0][rt] = y ; y = rt ; push_up ( rt ) ; return ; } split ( rs , x , y , k ) ; c[1][rt] = x ; x = rt ; push_up ( rt ) ; } void cut ( int rt , int fa ) { push_down ( rt ) ; if ( !c[1][rt] ) { c[1][fa] = c[0][rt] ; return ; } cut ( c[1][rt] , rt ) ; push_up ( rt ) ; } int find ( int rt , int k ) { int x , y , temp ; split ( rt , x , y , k ) ; printf ( "%d " , size[x] + k - 1 ) ; push_down ( x ) ; if ( size[x] == 1 ) return y ; if ( !c[1][x] ) { color ( c[0][x] ) ; return merge ( c[0][x] , y ) ; } cut ( x , x ) ; color ( x ) ; return merge ( x , y ) ; } void init () { tot = 0 ; mi[0] = 11111111 ; } } tree ; int main() { srand ( time ( NULL ) ) ; int n , i ; while ( scanf ( "%d" , &n ) == 1 && n ) { tree.init () ; for ( i = 1 ; i <= n ; i ++ ) scanf ( "%d" , &num[i] ) , pos[i] = i ; sort ( pos + 1 , pos + n + 1 , cmp ) ; for ( i = 1 ; i <= n ; i ++ ) num[pos[i]] = i ; int rt = 0 ; rt = tree.build ( 1 , n ) ; for ( i = 1 ; i < n ; i ++ ) rt = tree.find ( rt , i ) ; printf ( "%d\n" , n ) ; } return 0; } /* 20 8089 6286 8880 16892 5363 2990 4621 21227 6476 23659 31933 6505 23146 25222 30796 15967 24804 14923 19874 19874 20 7 4 8 11 3 1 2 14 5 16 20 6 15 18 19 10 17 9 13 12 6 7 7 6 9 12 11 9 18 11 18 19 20 16 17 16 20 19 19 20 6 7 7 6 9 12 11 9 18 11 18 20 13 18 15 20 18 20 19 20 */

hdu 1890 Robotic Sort(treap)

Robotic Sort