document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. using namespace std;
  2.  
  3. #include <iostream>
  4. #include <deque>
  5. #include <vector>
  6.  
  7. struct node
  8. {
  9.     int data;
  10.     struct node * left;
  11.     struct node * right;
  12.     struct node * parent;
  13.     bool visited;
  14. };
  15.  
  16. struct node * insert(int, int);
  17. void postorder(struct node *);
  18. struct node * getNode(int);
  19. struct node * findZone(struct node *, struct node *);
  20.  
  21. deque <int> d;
  22. vector <struct node *> v;
  23. int * in, * post, n;
  24.  
  25. int main(void)
  26. {
  27.     int q, z1, z2, num;
  28.    
  29.     cin >> n;
  30.    
  31.     in = new int[n];
  32.     post = new int[n];
  33.    
  34.     for(int i=0; i<n; i++)
  35.     {
  36.         cin >> num;
  37.         d.push_front(num);
  38.     }
  39.    
  40.     for(int i=0; i<n; i++)
  41.     {
  42.         cin >> in[i];
  43.     }
  44.    
  45.     struct node * root = insert(0, n-1);
  46.     if(root)
  47.     {
  48.         root->parent = NULL;
  49.         root->visited = false;
  50.     }
  51.     postorder(root);
  52.  
  53.     cin >> q;
  54.    
  55.     for(int i = 0; i<q; i++)
  56.     {
  57.         cin >> z1 >> z2;
  58.         struct node * z11 = getNode(z1);
  59.         struct node * z22 = getNode(z2);
  60.         if(z11 == z22)
  61.         {
  62.             cout << z11->data << endl;
  63.         }
  64.         else
  65.         {
  66.             struct node * z = findZone(z11, z22);
  67.             if(!z)
  68.               cout << root->data << endl;
  69.             else
  70.               cout << z->data << endl;
  71.         }
  72.         for(int j=0; j<n; j++)
  73.           v.at(j)->visited = false;
  74.     }
  75.    
  76.    
  77.     delete [] in;
  78.     delete [] post;
  79.     v.clear();
  80.    
  81.     return 0;
  82. }
  83.  
  84. struct node * insert(int begin, int end)
  85. {
  86.     if(begin > end)
  87.       return NULL;
  88.    
  89.     struct node * root = new struct node;
  90.     root->data = d.back();
  91.     root->left = NULL;
  92.     root->right = NULL;
  93.    
  94.     if(begin == end)
  95.     {
  96.         d.pop_back();
  97.         return root;
  98.     }
  99.    
  100.     int i = begin;
  101.     while(in[i] != d.back() && i < n)
  102.       i++;
  103.    
  104.     d.pop_back();
  105.    
  106.     root->left = insert(begin, i-1);
  107.     if(root->left)
  108.     {
  109.         root->left->parent = root;
  110.         root->left->visited = false;
  111.     }
  112.    
  113.     root->right = insert(i+1, end);
  114.     if(root->right)
  115.     {
  116.         root->right->parent = root;
  117.         root->right->visited = false;
  118.     }
  119.    
  120.     return root;
  121. }
  122.  
  123. void postorder(struct node * root)
  124. {
  125.     if(!root)
  126.       return;
  127.     postorder(root->left);
  128.     postorder(root->right);
  129.     v.push_back(root);
  130. }
  131.  
  132. struct node * getNode(int key)
  133. {
  134.     for(int i=0; i<n; i++)
  135.     {
  136.         if(v.at(i)->data == key)
  137.           return v.at(i);
  138.     }
  139.     return NULL;
  140. }
  141.  
  142. struct node * findZone(struct node * z1, struct node * z2)
  143. {
  144.     while(z1 || z2)
  145.     {
  146.         if(z1)
  147.         {
  148.             if(z1->visited)
  149.               return z1;
  150.             z1->visited = true;
  151.             z1 = z1->parent;
  152.         }
  153.         if(z2)
  154.         {
  155.             if(z2->visited)
  156.               return z2;
  157.             z2->visited = true;
  158.             z2 = z2->parent;
  159.         }
  160.     }
  161.     return NULL;
  162. }
');