fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int>G[100005];
  5. int anc[100005][20], dep[100005], n, cnt = 0;
  6. int mx[100005 * 4], mn[100005 * 4], id[100005], s[100005];
  7.  
  8. void dfs(int u, int fa, int deep)
  9. {
  10.     dep[u] = deep;
  11.     anc[u][0] = fa;
  12.     s[u] = ++cnt;
  13.     id[cnt] = u;
  14.     for (int i = 0; i < G[u].size(); i++) {
  15.         dfs(G[u][i], u, deep + 1);
  16.     }
  17. }
  18.  
  19. void init()
  20. {
  21.     for(int j = 1; j < 19; j++) {
  22.         for(int i = 1; i <= n; i++) {
  23.             anc[i][j] = anc[anc[i][j - 1]][j - 1];
  24.         }
  25.     }
  26. }
  27.  
  28. int lca(int p,int q)
  29. {
  30.     if (dep[p] < dep[q]) {
  31.         swap(p, q);
  32.     }
  33.     for (int i = 18; i >= 0; i--) {
  34.         if(dep[anc[p][i]] >= dep[q]) {
  35.             p=anc[p][i];
  36.         }
  37.     }
  38.     if (p == q) {
  39.         return dep[p] - 1;
  40.     }
  41.     for (int i = 18; i >= 0; i--) {
  42.         if (anc[p][i] != anc[q][i]) {
  43.             p = anc[p][i], q = anc[q][i];
  44.         }
  45.     }
  46.     return dep[anc[p][0]] - 1;
  47. }
  48.  
  49. int qmax(int o,int l,int r,int ql,int qr)
  50. {
  51.     if (l >= ql && r <= qr) {
  52.         return mx[o];
  53.     }
  54.     int ls = o * 2, rs = o * 2 + 1, m = (l + r) / 2, res = 0;
  55.     if (ql <= m) {
  56.         res = qmax(ls, l, m, ql, qr);
  57.     }
  58.     if (qr > m) {
  59.         res = max(res, qmax(rs, m + 1, r, ql, qr));
  60.     }
  61.     return res;
  62. }
  63.  
  64. int qmin(int o,int l,int r,int ql,int qr)
  65. {
  66.     if (l >= ql && r <= qr) {
  67.         return mn[o];
  68.     }
  69.     int ls = o * 2, rs = o * 2 + 1, m = (l + r) / 2, res = 1e8;
  70.     if (ql <= m) {
  71.         res = qmin(ls, l, m, ql, qr);
  72.     }
  73.     if (qr > m) {
  74.         res = min(res, qmin(rs, m + 1, r, ql, qr));
  75.     }
  76.     return res;
  77. }
  78.  
  79. void up(int o, int l, int r, int k, int v)
  80. {
  81.     if (l == r) {
  82.         mx[o] = mn[o] = v;
  83.         return;
  84.     }
  85.     int ls = o * 2, rs = o * 2 + 1, m = (l + r) / 2;
  86.     if (k <= m) {
  87.         up(ls, l, m, k, v);
  88.     }
  89.     else {
  90.         up(rs, m + 1, r, k, v);
  91.     }
  92.     mx[o] = max(mx[ls], mx[rs]);
  93.     mn[o] = min(mn[ls], mn[rs]);
  94. }
  95.  
  96. int main() {
  97.     int q, x, l, r;
  98.     scanf("%d %d", &n, &q);
  99.     for (int i = 2; i <= n; i++) {
  100.         scanf("%d", &x);
  101.         G[x].push_back(i);
  102.     }
  103.     dfs(1, 0, 1);
  104.     init();
  105.     for(int i = 1; i <= n; i++) {
  106.         up(1, 1, n, i, s[i]);
  107.     }
  108.     while (q--) {
  109.         scanf("%d %d", &l, &r);
  110.         int la = qmin(1, 1, n, l, r);
  111.         int rb = qmax(1, 1, n, l, r);
  112.         up(1, 1, n, id[la], 1e8);
  113.         int a = qmin(1, 1, n, l, r);
  114.         up(1, 1, n, id[la], la);
  115.         up(1, 1, n, id[rb], 0);
  116.         int b = qmax(1, 1, n, l, r);
  117.         up(1, 1, n, id[rb], rb);
  118.         int t1 = lca(id[la], id[b]), t2 = lca(id[a], id[rb]);
  119.         if (t1 >= t2) {
  120.             printf("%d %d\n", id[rb], t1);
  121.         }
  122.         else {
  123.             printf("%d %d\n", id[la], t2);
  124.         }
  125.     }
  126.     return 0;
  127. }
Success #stdin #stdout 0s 29688KB
comments (?)
stdin
copy 
11 5
1 1 3 3 3 4 2 7 7 6
4 6
4 8
1 11
9 11
8 11
stdout
copy 
6 1
8 1
11 0
11 3
8 1
https://ideone.com/moSx0t
language:
C++14 (gcc 8.3)
created:
5 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!