Malinovsky239

Untitled

Sep 26th, 2012
520
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <vector>
  2. #include <list>
  3. #include <map>
  4. #include <set>
  5. #include <deque>
  6. #include <queue>
  7. #include <bitset>
  8. #include <sstream>
  9. #include <algorithm>
  10. #include <functional>
  11. #include <numeric>
  12. #include <iostream>
  13. #include <cstdio>
  14. #include <cmath>
  15. #include <cstdlib>
  16. #include <ctime>
  17. #include <cstring>
  18. #include <cassert>
  19.  
  20. using namespace std;
  21.  
  22. #define forn(i, n) for(int i = 0; i < int(n); ++i)
  23. #define for1(i, n) for(int i = 1; i <= int(n); ++i)
  24. #define ford(i, n) for(int i = int(n) - 1; i >= 0; --i)
  25. #define fore(i, l, r) for(int i = int(l); i < int(r); ++i)
  26. #define sz(v) int((v).size())
  27. #define all(v) (v).begin(), (v).end()
  28. #define pb push_back
  29. #define X first
  30. #define Y second
  31. #define mp make_pair
  32. #define debug(x) {cerr << #x << " = " << x << endl;}
  33. template<typename T> inline T abs(T a){ return ((a < 0) ? -a : a); }
  34. template<typename T> inline T sqr(T a){ return a * a; }
  35.  
  36. typedef long long li;
  37. typedef long double ld;
  38. typedef pair<int, int> pt;
  39.  
  40. const int INF = (int)1E9 + 7;
  41. const ld EPS = 1E-9;
  42. const ld PI = 3.1415926535897932384626433832795;
  43.  
  44. const int NMAX = 300000;
  45. const int LOG = 20;
  46.  
  47. int n, m;
  48. vector<int> g[NMAX];
  49.  
  50. int p[LOG][NMAX], dep[NMAX], tin[NMAX], tout[NMAX], timer = 0, ord[NMAX];
  51.  
  52. struct node{
  53.     int sum;
  54.     node *l;
  55.     node *r;
  56.     node(){
  57.         sum = 0, l = 0, r = 0;
  58.     }
  59. };
  60.  
  61. const int SZBUF = 4*NMAX + LOG * 110000 * 4;
  62. node buf[SZBUF];
  63. int szbuf = 0;
  64.  
  65. typedef node* tree;
  66.  
  67. tree allocate(){
  68.     if(szbuf == SZBUF)
  69.         throw;
  70.     tree cur = &buf[szbuf++];
  71.     return cur;
  72. }
  73.  
  74. tree copy(tree val){
  75.     if(!val) return allocate();
  76.     tree ans = allocate();
  77.     ans->sum = val->sum,
  78.     ans->l = val->l,
  79.     ans->r = val->r;
  80.     return ans;
  81. }
  82.  
  83. int get_sum(tree t){
  84.     if(!t) return 0;
  85.     return t->sum;
  86. }
  87.  
  88. tree upd(int pos, int val, tree idx, int l, int r){
  89.     tree t = copy(idx);
  90.     if(l == r){
  91.         t->sum += val;
  92.         return t;
  93.     }
  94.  
  95.     int mid = (l + r) >> 1;
  96.  
  97.     if(pos <= mid)
  98.         t->l = upd(pos, val, t->l, l, mid);
  99.     else
  100.         t->r = upd(pos, val, t->r, mid+1, r);
  101.     t->sum = get_sum(t->l) + get_sum(t->r);
  102.     return t;
  103. }
  104.  
  105. int sum(int l, int r, tree idx, int tl, int tr){
  106.     if(!idx) return 0;
  107.  
  108.     if(l == tl && r == tr){
  109.         return idx->sum;
  110.     }
  111.  
  112.     int ans = 0, mid = (tl + tr) >> 1;
  113.     if(l <= mid)
  114.         ans += sum(l, min(mid, r), idx->l, tl, mid);
  115.     if(r >= mid + 1)
  116.         ans += sum(max(l, mid+1), r, idx->r, mid+1, tr);
  117.     return ans;
  118. }
  119.  
  120. void dfs(int v){
  121.     ord[timer] = v;
  122.     tin[v] = timer++;
  123.  
  124.     fore(i, 1, LOG)
  125.         p[i][v] = p[i - 1][p[i - 1][v]];
  126.     forn(i, sz(g[v])){
  127.         int u = g[v][i];
  128.         dep[u] = dep[v] + 1;
  129.         dfs(u);
  130.     }
  131.  
  132.     ord[timer] = v;
  133.     tout[v] = timer++;
  134. }
  135.  
  136. int lca(int a, int b){
  137.     if(dep[a] < dep[b]) swap(a, b);
  138.     ford(i, LOG)
  139.         if(dep[p[i][a]] > dep[b])
  140.             a = p[i][a];
  141.     if(dep[a] != dep[b])
  142.         a = p[0][a];
  143.     assert(dep[a] == dep[b]);
  144.     ford(i, LOG)
  145.         if(p[i][a] != p[i][b])
  146.             a = p[i][a], b = p[i][b];
  147.     if(a != b)
  148.         a = p[0][a], b = p[0][b];
  149.     assert(a == b);
  150.     return a;
  151. }
  152.  
  153. tree times[NMAX];
  154.  
  155. int getSum(int cur_time, int a, int b){
  156.     if(dep[a] > dep[b]) swap(a, b);
  157.     int l = tin[a], r = tin[b];
  158.     assert(l <= r);
  159.  
  160.     return sum(l, r, times[cur_time], 0, 2*n-1);
  161. }
  162.  
  163. int getGood(int t1, int t2, int a, int b){
  164.     if(dep[a] > dep[b]) swap(a, b);
  165.     int cnt = dep[b] - dep[a] + 1;
  166.     return cnt - (getSum(t1, a, b) - getSum(t2, a, b));
  167. }
  168.  
  169. int get_kth(int k, int t1, int t2, int a, int b){
  170.     if(dep[a] < dep[b]) swap(a, b);
  171.  
  172.     int sa = a;
  173.  
  174. //    cerr << "kth:" << k << " " << a << " " << b << endl;
  175.     ford(i, LOG){
  176.         if(dep[p[i][a]] >= dep[b] && getGood(t1, t2, sa, p[i][a]) < k)
  177.             a = p[i][a];    
  178.     }
  179. //    cerr << a << endl;
  180.     if(dep[p[0][a]] >= dep[b] && getGood(t1, t2, sa, p[0][a]) < k){
  181.         a = p[0][a];
  182.     }
  183.  
  184.     return getGood(t1, t2, sa, a) == k ? a : p[0][a];
  185. }
  186.  
  187. int main() {
  188.     #ifdef myproject
  189.     freopen("input.txt", "rt", stdin);
  190.     //freopen("output.txt", "wt", stdout);
  191.     #endif
  192.     scanf("%d", &n);
  193.  
  194.     int r = -1;
  195.     forn(i, n){
  196.         int pi;
  197.         scanf("%d", &pi);
  198.         pi--;
  199.  
  200.         if(pi != -1){
  201.             g[pi].pb(i);
  202.         }else{
  203.             r = i;
  204.         }
  205.  
  206.         p[0][i] = (pi == -1) ? i : pi;
  207.     }    
  208.    
  209.     dfs(r);
  210.  
  211.     scanf("%d", &m);
  212.     forn(i, m){
  213.         int t;
  214.         scanf("%d", &t);
  215.  
  216.         if(t == 1){
  217.             int idx;
  218.             scanf("%d", &idx);
  219.             idx--;
  220.             times[i + 1] = upd(tin[idx], 1, times[i], 0, 2*n-1);
  221.             times[i + 1] = upd(tout[idx], -1, times[i + 1], 0, 2*n-1);
  222.         }else{
  223.             int a, b, ki, yi;
  224.             scanf("%d%d%d%d", &a, &b, &ki, &yi);
  225.             --a, --b;
  226.             int mid = lca(a, b);
  227.  
  228.             times[i + 1] = times[i];
  229.  
  230.             int goodA = getGood(i+1, yi, a, a);
  231.             int goodMid = getGood(i+1, yi, mid, mid);
  232.  
  233.             ki += goodA;
  234.  
  235.             int part1 = getGood(i+1, yi, a, mid),
  236.                 part2 = getGood(i+1, yi, b, mid);
  237.  
  238.             int allk = part1 + part2 - goodMid;
  239.  
  240. //            cerr << a+1 << " " << mid+1 << " " << b+1 << endl;
  241. //            cerr << "+" << part1 << " " << part2 << " " << allk << " " << ki << endl;
  242.  
  243.             if(allk < ki)
  244.                 puts("-1");
  245.             else{
  246.                 int ans = -1;
  247.                 if(ki <= part1)
  248.                     ans = get_kth(ki, i+1, yi, a, mid);
  249.                 else{
  250.                     ki -= part1;
  251.                     ki += goodMid;
  252.  
  253.                     assert(ki <= part2);
  254.  
  255.                     //cerr << ki << " " << part2 - ki + 1 << " " << b << " " << mid << endl;
  256.                     ans = get_kth(part2 - ki + 1, i+1, yi, b, mid);
  257.                 }
  258.  
  259.                 printf("%d\n", (ans == b ? -1 : ans + 1));
  260.             }
  261.         }
  262.     }
  263.  
  264.     #ifdef myproject
  265.     cerr << "Time = " << clock() << endl;
  266.     cerr << "SZBUF = " << szbuf << endl;
  267.     #endif
  268.  
  269.     return 0;
  270. }
RAW Paste Data