fork download 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstdio>
  4. #include <cstdlib>
  5.  
  6. //#define ONLINE_JUDGE
  7.  
  8. const int MAXN = 131072;
  9. const int MAX_NODE_N = MAXN*2+1;
  10. using namespace std;
  11.  
  12. struct Element
  13. {
  14.     int number;//number from input
  15.     int index;//order from input
  16. };
  17.  
  18. bool operator < (const Element &A, const Element &B)
  19. {
  20.     return A.number < B.number;//sort by num
  21. }
  22.  
  23. Element num[MAXN];
  24. int segTreeRMQ[MAX_NODE_N];
  25.  
  26. void readInputArr(int N)
  27. {
  28.     for(int i=0; i<N; i++)
  29.     {
  30.         num[i].index = i;
  31.         scanf("%d",&num[i].number);
  32.     }
  33. }
  34.  
  35. #ifndef ONLINE_JUDGE
  36. void testArr(int N)
  37. {
  38.     puts("-------------");
  39.     puts("Test read : (num,index)");
  40.     for(int i=0; i<N; i++)
  41.         printf(" (%d,%d)", num[i].number, num[i].index);
  42.     puts("\n-------------");
  43. }
  44. #endif // ONLINE_JUDGE
  45. //referenece
  46. //http://w...content-available-to-author-only...r.com/tc?d1=tutorials&d2=lowestCommonAncestor&module=Static
  47.  
  48. //almost the same code, OMG
  49. void initializeTree(int node_i, int b, int e, int M[MAX_NODE_N], Element A[MAXN], int N)
  50. {
  51.     if(b==e)
  52.         M[node_i] = b;//position of min "index from input"
  53.     else
  54.     {
  55.         //node_i : heap style
  56.         initializeTree(2*node_i, b, (b+e)/2 , M, A, N);//init left
  57.         initializeTree(2*node_i+1, (b+e)/2+1, e, M, A, N);//init right
  58.         //b,e 1~N
  59.         //Arr 0~N
  60.         if(A[M[2*node_i]].index<=A[M[2*node_i+1]].index)
  61.             M[node_i] = M[2*node_i];//choose left child min
  62.         else
  63.             M[node_i] = M[2*node_i+1];
  64.     }
  65.  
  66.     //debug info
  67.     #ifndef ONLINE_JUDGE
  68.     printf("segT[%d][%d,%d]=%d, A[%d].index=%d\n",node_i, b, e, M[node_i], A[M[node_i]]);
  69.     #endif // ONLINE_JUDGE
  70. }
  71.  
  72. //i, j is query range i<=j
  73. int query(int node_i, int b, int e, int M[MAX_NODE_N], Element A[MAXN], int i, int j)
  74. {
  75.     int p1, p2;
  76.  
  77.     //no intersection
  78.     //A.lesser > B.greater or A.greater < B.lesser
  79.     // [i,j]
  80.     //
  81.     //        [b,e]
  82.     //--------------
  83.     //         [i,j]
  84.     // [b,e]
  85.     if(i>e || j<b)
  86.         return -1;//NULL
  87.  
  88.     //intersect, included
  89.     // [i,           j]
  90.     //       [b,e]
  91.     if(b>=i&&e<=j)
  92.         return M[node_i];
  93.  
  94.     //intersect, not include
  95.     p1 = query(2*node_i, b, (b+e)/2, M, A, i, j);
  96.     p2 = query(2*node_i+1, (b+e)/2+1, e, M, A, i, j);
  97.  
  98.     if(p1==-1)
  99.         return p2;//M[node]=p2?
  100.     if(p2==-1)
  101.         return p1;
  102.  
  103.     if(A[p1].index<=A[p2].index)
  104.         return p1;
  105.     else
  106.         return p2;
  107.  
  108. }
  109.  
  110. const int segTreeRootI = 1;
  111. void fake_preorder_tra(int i, int j, int N, int M[MAX_NODE_N], Element A[MAXN])
  112. {
  113.     int rootPos = query(segTreeRootI, 0, N-1, M, A, i,j);//root
  114.     if(rootPos>=0&&rootPos<N)
  115.     {
  116.         if(A[rootPos].index==0)
  117.             printf("%d", A[rootPos].number);
  118.         else
  119.             printf(" %d", A[rootPos].number);
  120.  
  121.  
  122.         if(i!=j)//not leave
  123.         {
  124.          //left
  125.             fake_preorder_tra(i,rootPos-1, N, M, A);
  126.         //right
  127.             fake_preorder_tra(rootPos+1,j, N, M, A);
  128.         }
  129.  
  130.     }
  131. }
  132.  
  133. int main()
  134. {
  135.     int N;
  136.     while(scanf("%d",&N)!=EOF)
  137.     {
  138.         readInputArr(N);
  139.  
  140.         //debug info
  141.         #ifndef ONLINE_JUDGE
  142.         testArr(N);
  143.         #endif // ONLINE_JUDGE
  144.  
  145.         std::sort(num,num+N);//get Inorder traversal
  146.  
  147.         //debug info
  148.         #ifndef ONLINE_JUDGE
  149.         printf("sorted\n");
  150.         testArr(N);
  151.         #endif // ONLINE_JUDGE
  152.  
  153.  
  154.         initializeTree(segTreeRootI,0,N-1,segTreeRMQ,num,N);
  155.         fake_preorder_tra(0,N-1,N,segTreeRMQ,num);
  156.         putchar('\n');
  157.     }
  158.     return 0;
  159. }
  160.  
Success #stdin #stdout 0s 5152KB
comments (?)
stdin 
5
0 1 2 4 3
5
0 2 4 1 3
5
3 1 4 2 0
5
1 4 2 0 3
5
0 4 3 2 1
stdout 
0 1 2 4 3
0 2 1 4 3
3 1 0 2 4
1 0 4 2 3
0 4 3 2 1
https://ideone.com/dwEeRp
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!