Malinovsky239

Untitled

Sep 26th, 2012
602
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstdlib>
  4. #include <cstring>
  5. #include <cassert>
  6. #include <complex>
  7. #include <cstdio>
  8. #include <vector>
  9. #include <cctype>
  10. #include <string>
  11. #include <ctime>
  12. #include <cmath>
  13. #include <set>
  14. #include <map>
  15.  
  16. typedef long double LD;
  17. typedef long long LL;
  18.  
  19. using namespace std;
  20.  
  21. #define sz(A) (int)(A).size()
  22. #define mp make_pair
  23. #define pb push_back
  24.  
  25. const int N = int(1e5 + 5), INF = int(1e9);
  26.  
  27. struct node {
  28.     int l, r, val;
  29.  
  30.     node() {}
  31.  
  32.     node(int a, int b, int c) {
  33.         l = a, r = b, val = c;
  34.     }
  35. };
  36.  
  37. vector<int> graph[N];
  38. int n, root, m, par[N];
  39.  
  40. int sz[N], heavy[N], depth[N];
  41.  
  42. int first[N], t = 0, sz_lca;
  43. pair<int, int> times[2 * N], tree_lca[8 * N];
  44.  
  45. bool in_decomp[N];
  46. int num_trees, num_tree_in[N], pos_tree_in[N], sz_ptree[N];
  47. vector<int> tree[N];
  48. vector< pair<int, int> > roots[N];
  49. vector<node> ptree[N];
  50.  
  51. void dfs(int v, int d) {
  52.     depth[v] = d;
  53.     sz[v] = 1;
  54.  
  55.     heavy[v] = -1;
  56.     int mx = 0;
  57.  
  58.     for (int i = 0; i < sz(graph[v]); i++) {
  59.         int to = graph[v][i];
  60.        
  61.         if (!first[v]) first[v] = t + 1;
  62.         times[t++] = mp(d, v);
  63.  
  64.         if (!first[to]) first[to] = t + 1;
  65.         times[t++] = mp(d + 1, to);
  66.  
  67.         dfs(to, d + 1);
  68.  
  69.         sz[v] += sz[to];       
  70.  
  71.         if (sz[to] > mx) {
  72.             mx = sz[to];
  73.             heavy[v] = to;
  74.         }
  75.     }
  76. }
  77.  
  78. void build_lca() {
  79.     sz_lca = 1;
  80.     while (sz_lca < t) sz_lca <<= 1;
  81.  
  82.     for (int i = sz_lca; i < sz_lca + t; i++)
  83.         tree_lca[i] = times[i - sz_lca];
  84.  
  85.     for (int i = sz_lca + t; i < 2 * sz_lca; i++)      
  86.         tree_lca[i] = mp(INF, -1);
  87.  
  88.     for (int i = sz_lca - 1; i > 0; i--)
  89.         tree_lca[i] = min(tree_lca[i * 2], tree_lca[i * 2 + 1]);
  90. }
  91.  
  92. pair<int, int> min_lca(int l, int r, int L, int R, int v) {
  93.     if (r <= L || R <= l) return mp(INF, -1);
  94.     if (l <= L && R <= r) return tree_lca[v];
  95.     int mid = (L + R) / 2;
  96.     return min( min_lca(l, r, L, mid, v * 2), min_lca(l, r, mid, R, v * 2 + 1) );
  97. }
  98.  
  99. int lca(int v1, int v2) {
  100.     if (first[v1] > first[v2]) swap(v1, v2);
  101.     return min_lca(first[v1], first[v2] + 1, 1, sz_lca + 1, 1).second;     
  102. }
  103.  
  104. void dfs_heavy(int v) {
  105.     if (!in_decomp[v]) {
  106.         int now = v;
  107.         while (now != -1) {
  108.             tree[num_trees].pb(now);
  109.             in_decomp[now] = 1;
  110.             num_tree_in[now] = num_trees;
  111.             pos_tree_in[now] = sz(tree[num_trees]);
  112.             now = heavy[now];
  113.         }
  114.         num_trees++;
  115.     }
  116.  
  117.     for (int i = 0; i < sz(graph[v]); i++)
  118.         dfs_heavy(graph[v][i]);
  119. }
  120.  
  121. node create_node(int l, int r, int num_t) {
  122.     return node(l, r, ptree[num_t][l].val + ptree[num_t][r].val);      
  123. }
  124.  
  125. int update_ptree(int num_t, int pos, int L, int R, int v, int new_val) {
  126.     if (L + 1 == R) {
  127.         ptree[num_t].pb( create_node(0, 0, num_t) );
  128.         ptree[num_t][ sz(ptree[num_t]) - 1 ].val = new_val;
  129.         return sz(ptree[num_t]) - 1;               
  130.     }
  131.    
  132.     int mid = (L + R) / 2;
  133.  
  134.     if (pos < mid) {
  135.         int new_v = update_ptree(num_t, pos, L, mid, ptree[num_t][v].l, new_val);      
  136.         ptree[num_t].pb( create_node(new_v, ptree[num_t][v].r, num_t) );
  137.     }
  138.     else {
  139.         int new_v = update_ptree(num_t, pos, mid, R, ptree[num_t][v].r, new_val);
  140.         ptree[num_t].pb( create_node(ptree[num_t][v].l, new_v, num_t) );
  141.     }
  142.     assert(R - L >= ptree[num_t][sz(ptree[num_t]) - 1].val);
  143.     return sz(ptree[num_t]) - 1;
  144. }
  145.  
  146. int sum_ptree(int num_t, int l, int r, int L, int R, int v1, int v2) {
  147.     if (r <= L || R <= l) return 0;
  148.     if (l <= L && R <= r) return (R - L) - (ptree[num_t][v1].val - ptree[num_t][v2].val);
  149.     int mid = (L + R) / 2;
  150.     return sum_ptree(num_t, l, r, L, mid, ptree[num_t][v1].l, ptree[num_t][v2].l) + sum_ptree(num_t, l, r, mid, R, ptree[num_t][v1].r, ptree[num_t][v2].r);
  151. }
  152.  
  153. int num_version(int tree, int timer) {
  154.     int l = 0, r = sz(roots[tree]);
  155.     while (l + 1 < r) {
  156.         int mid = (l + r) / 2;
  157.         if (roots[tree][mid].first <= timer)
  158.             l = mid;
  159.         else
  160.             r = mid;
  161.     }
  162.     return l;
  163. }
  164.  
  165. int main() {
  166.     scanf("%d", &n);
  167.     for (int i = 1; i <= n; i++) {
  168.         scanf("%d", &par[i]);  
  169.  
  170.         if (par[i] == 0)
  171.             root = i;
  172.         else
  173.             graph[ par[i] ].pb(i);
  174.     }
  175.  
  176.     dfs(root, 1);
  177.  
  178.     build_lca();
  179.  
  180.     dfs_heavy(root);   
  181.  
  182.     for (int i = 0; i < num_trees; i++) {
  183.         int number = sz(tree[i]);
  184.    
  185.         sz_ptree[i] = 1;
  186.         while (sz_ptree[i] < number) sz_ptree[i] <<= 1;
  187.         ptree[i].resize(sz_ptree[i] * 2);
  188.         roots[i].pb(mp(0, 1));
  189.         for (int j = 1; j < sz_ptree[i]; j++) {
  190.             ptree[i][j].l = j * 2;
  191.             ptree[i][j].r = j * 2 + 1;     
  192.         }
  193.         for (int j = sz_ptree[i]; j < 2 * sz_ptree[i]; j++) {
  194.             if (j - sz_ptree[i] < number)
  195.                 ptree[i][j].val = 1;
  196.             else   
  197.                 ptree[i][j].val = 0;
  198.         }
  199.         for (int j = sz_ptree[i] - 1; j > 0; j--) {
  200.             ptree[i][j].val = ptree[i][j * 2].val + ptree[i][j * 2 + 1].val;
  201.         }
  202.     }
  203.  
  204.     scanf("%d", &m);
  205.  
  206.     for (int i = 0; i < m; i++) {
  207.         int type;
  208.         scanf("%d", &type);
  209.  
  210.         if (type == 1) {
  211.             int v;
  212.             scanf("%d", &v);
  213.             int t_num = num_tree_in[v];
  214.             int prev_sz = sz(roots[t_num]);
  215.             roots[t_num].pb(mp(i + 1, update_ptree(t_num, pos_tree_in[v], 1, sz_ptree[t_num] + 1, roots[t_num][prev_sz - 1].second, 0)));
  216.         }
  217.         else {
  218.             int v1, v2, k, start;
  219.            
  220.             scanf("%d%d%d%d", &v1, &v2, &k, &start);
  221.  
  222.             int v3 = lca(v1, v2), now;
  223.  
  224.             bool ans_given = 0;
  225.  
  226.             int num_t = num_tree_in[v3];
  227.             int vers = num_version(num_t, start), num_r = sz(roots[num_t]);
  228.  
  229.             int root_val = sum_ptree(num_t, pos_tree_in[v3], pos_tree_in[v3] + 1, 1, sz_ptree[num_t] + 1, roots[num_t][vers].second, roots[num_t][num_r - 1].second);
  230.             int start_pos = pos_tree_in[v3];
  231.             if (v3 == v2 || v3 == v1)
  232.                 start_pos++;
  233.  
  234.             now = par[v1];
  235.             while (depth[now] >= depth[v3] && now != v2) {
  236.                 int num_t = num_tree_in[now], num_r = sz(roots[num_t]), sum = 0;
  237.                 int vers = num_version(num_t, start);
  238.  
  239.                 if (depth[v3] < depth[ tree[num_t][0] ]) {                 
  240.                     sum = sum_ptree(num_t, 1, pos_tree_in[now] + 1, 1, sz_ptree[num_t] + 1, roots[num_t][vers].second, roots[num_t][num_r - 1].second);                  
  241.                 }
  242.                 else {
  243.                     sum = sum_ptree(num_t, start_pos, pos_tree_in[now] + 1, 1, sz_ptree[num_t] + 1, roots[num_t][vers].second, roots[num_t][num_r - 1].second);
  244.                 }          
  245.                 if (sum < k) {
  246.                     k -= sum;
  247.                 }
  248.                 else {                     
  249.                     k = sum - k + 1;
  250.                     int left_b = 1;
  251.                     if (num_t == num_tree_in[v3])
  252.                         left_b = start_pos;                                            
  253.                                            
  254.                     int r1 = roots[num_t][num_r - 1].second, r2 = roots[num_t][vers].second, L = 1, R = sz_ptree[num_t] + 1;
  255.  
  256.                     while (L + 1 < R) {
  257.                         int mid = (L + R) / 2;                     
  258.  
  259.                         if ( sum_ptree(num_t, left_b, pos_tree_in[now] + 1, L, mid, ptree[num_t][r2].l, ptree[num_t][r1].l) < k) {                         
  260.                             k -= sum_ptree(num_t, left_b, pos_tree_in[now] + 1, L, mid, ptree[num_t][r2].l, ptree[num_t][r1].l);                           
  261.                             r1 = ptree[num_t][r1].r;
  262.                             r2 = ptree[num_t][r2].r;
  263.                             L = mid;                           
  264.                         }
  265.                         else {                         
  266.                             r1 = ptree[num_t][r1].l;
  267.                             r2 = ptree[num_t][r2].l;
  268.                             R = mid;
  269.                         }  
  270.                     }                            
  271.  
  272.                     printf("%d\n", tree[num_t][L - 1]);
  273.                     ans_given = 1;
  274.                     break;
  275.                 }
  276.  
  277.                 now = par[ tree[num_t][0] ];
  278.             }
  279.  
  280.             if (ans_given) continue;           
  281.  
  282.             now = par[v2];         
  283.  
  284.             int sum_path = 0;
  285.  
  286.             if (v3 != v2 && v3 != v1)
  287.                 k += root_val;
  288.  
  289.             while (depth[now] >= depth[v3] && now != v1) {
  290.                 int num_t = num_tree_in[now], num_r = sz(roots[num_t]);
  291.                 int vers = num_version(num_t, start);
  292.  
  293.                 if (depth[v3] < depth[ tree[num_t][0] ]) {
  294.                     sum_path += sum_ptree(num_t, 1, pos_tree_in[now] + 1, 1, sz_ptree[num_t] + 1, roots[num_t][vers].second, roots[num_t][num_r - 1].second);                    
  295.                 }
  296.                 else {
  297.                     sum_path += sum_ptree(num_t, start_pos, pos_tree_in[now] + 1, 1, sz_ptree[num_t] + 1, roots[num_t][vers].second, roots[num_t][num_r - 1].second);
  298.                 }                                      
  299.  
  300.                 now = par[ tree[num_t][0] ];               
  301.             }
  302.  
  303.             if (sum_path < k) {
  304.                 printf("-1\n");
  305.                 continue;
  306.             }
  307.  
  308.             k = sum_path - k + 1;
  309.  
  310.             now = par[v2];
  311.  
  312.             while (depth[now] >= depth[v3] && now != v1) {
  313.                 int num_t = num_tree_in[now], num_r = sz(roots[num_t]), sum = 0;
  314.                 int vers = num_version(num_t, start);
  315.  
  316.                 if (depth[v3] < depth[ tree[num_t][0] ]) {
  317.                     sum = sum_ptree(num_t, 1, pos_tree_in[now] + 1, 1, sz_ptree[num_t] + 1, roots[num_t][vers].second, roots[num_t][num_r - 1].second);                      
  318.                 }
  319.                 else {
  320.                     sum = sum_ptree(num_t, start_pos, pos_tree_in[now] + 1, 1, sz_ptree[num_t] + 1, roots[num_t][vers].second, roots[num_t][num_r - 1].second);
  321.                 }
  322.        
  323.                 if (sum < k) {
  324.                     k -= sum;
  325.                 }
  326.                 else {                 
  327.                     k = sum - k + 1;
  328.                     int left_b = 1;
  329.                     if (num_t == num_tree_in[v3])
  330.                         left_b = start_pos;                                            
  331.  
  332.                     int r1 = roots[num_t][num_r - 1].second, r2 = roots[num_t][vers].second, L = 1, R = sz_ptree[num_t] + 1;
  333.  
  334.                     while (L + 1 < R) {
  335.                         int mid = (L + R) / 2;                     
  336.  
  337.                         if ( sum_ptree(num_t, left_b, pos_tree_in[now] + 1, L, mid, ptree[num_t][r2].l, ptree[num_t][r1].l) < k) {                         
  338.                             k -= sum_ptree(num_t, left_b, pos_tree_in[now] + 1, L, mid, ptree[num_t][r2].l, ptree[num_t][r1].l);                               
  339.                             r1 = ptree[num_t][r1].r;
  340.                             r2 = ptree[num_t][r2].r;
  341.                             L = mid;                           
  342.                         }
  343.                         else {                         
  344.                             r1 = ptree[num_t][r1].l;
  345.                             r2 = ptree[num_t][r2].l;
  346.                             R = mid;
  347.                         }  
  348.                     }                            
  349.  
  350.                     printf("%d\n", tree[num_t][L - 1]);                    
  351.                     break;
  352.                 }
  353.  
  354.                 now = par[ tree[num_t][0] ];
  355.             }
  356.         }
  357.     }
  358.  
  359.     return 0;
  360. }
RAW Paste Data