peltorator

!Персистентное Дерево Отрезков

Dec 5th, 2017
278
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cstdio>
  4. #include <map>
  5. #include <algorithm>
  6. #include <math.h>
  7. #include <string>
  8. #include <cstring>
  9. #include <set>
  10. #include <queue>
  11. #include <unordered_set>
  12. #include <unordered_map>
  13.  
  14. using namespace std;
  15.  
  16. typedef long long ll;
  17. typedef double ld;
  18.  
  19. const int N = 100001, INF = 1e9 + 7;
  20.  
  21. struct Node
  22. {
  23.     int min;
  24.     Node *left;
  25.     Node *right;
  26.     Node(int num, Node* l, Node* r):
  27.         min(num),
  28.         left(l),
  29.         right(r) {}
  30. };
  31.  
  32. Node* build(int l, int r)
  33. {
  34.     if (l == r)
  35.         return new Node(INF, 0, 0);
  36.     int mid = (r + l) / 2;
  37.     Node *v = build(l, mid);
  38.     return new Node(INF, v, v);
  39. }
  40.  
  41. Node* update(Node *v, int p, int val, int l, int r)
  42. {
  43.     if (p < l || p > r)
  44.         return v;
  45.     if (l == r)
  46.         return new Node(min(v->min, val), 0, 0);
  47.     int mid = (r + l) / 2;
  48.     return new Node(min(v->min, val), update(v->left, p, val, l, mid), update(v->right, p, val, mid + 1, r));
  49. }
  50.  
  51. int find_min(Node *v, int l, int r, int ql, int qr)
  52. {
  53.     if (r < ql || l > qr)
  54.         return INF;
  55.     if (ql <= l && r <= qr)
  56.         return v->min;
  57.     int mid = (r + l) / 2;
  58.     return min(find_min(v->left, l, mid, ql, qr), find_min(v->right, mid + 1, r, ql, qr));
  59. }
  60.  
  61. int a[N];
  62. vector<int> g[N];
  63. int used[N];
  64. int lvl[N], down[N];
  65. Node* tree[N];
  66.  
  67. void dfs(int v)
  68. {
  69.     if (!lvl[v])
  70.         lvl[v] = 1;
  71.     used[v] = 1;
  72.     down[v] = 1;
  73.     for (int i = 0; i + 1 < g[v].size(); i++)
  74.         if (used[g[v][i]])
  75.             swap(g[v][i], g[v][i + 1]);
  76.     if (g[v].size() && used[g[v].back()])
  77.         g[v].pop_back();
  78.     for (int i = 0; i < g[v].size(); i++)
  79.     {
  80.         lvl[g[v][i]] = lvl[v] + 1;
  81.         dfs(g[v][i]);
  82.         down[v] = max(down[v], down[g[v][i]] + 1);
  83.     }
  84.     for (int i = 1; i < g[v].size(); i++)
  85.         if (down[g[v][0]] < down[g[v][i]])
  86.                 swap(g[v][0], g[v][i]);
  87. }
  88.  
  89. int n;
  90.  
  91. void dfs1(int v)
  92. {
  93.     used[v] = 1;
  94.     if (!g[v].size())
  95.     {
  96.         tree[v] = build(1, n);
  97.         tree[v] = update(tree[v], lvl[v], a[v], 1, n);
  98.         return;
  99.     }
  100.     for (int i = 0; i < g[v].size(); i++)
  101.     {
  102.         dfs1(g[v][i]);
  103.         if (!i)
  104.         {
  105.             tree[v] = tree[g[v][i]];
  106.             tree[v] = update(tree[v], lvl[v], a[v], 1, n);
  107.             continue;
  108.         }
  109.         for (int j = lvl[g[v][i]]; j <= lvl[g[v][i]] + down[g[v][i]] - 1; j++)
  110.             tree[v] = update(tree[v], j, find_min(tree[g[v][i]], 1, n, j, j), 1, n);
  111.     }
  112.     return;
  113. }
  114.  
  115. int main()
  116. {
  117.     ios::sync_with_stdio(0); cin.tie(0);
  118.     int r;
  119.     cin >> n >> r;
  120.     for (int i = 1; i <= n; i++)
  121.         cin >> a[i];
  122.     for (int i = 1; i < n; i++)
  123.     {
  124.         int x, y;
  125.         cin >> x >> y;
  126.         g[x].push_back(y);
  127.         g[y].push_back(x);
  128.     }
  129.     dfs(r);
  130.     for (int i = 1; i <= n; i++)
  131.         used[i] = 0;
  132.     dfs1(r);
  133.     int m;
  134.     cin >> m;
  135.     int last = 0;
  136.     for (int i = 0; i < m; i++)
  137.     {
  138.         int p, q;
  139.         cin >> p >> q;
  140.         int v = (p + last) % n + 1, k = (q + last) % n;
  141.         last = find_min(tree[v], 1, n, lvl[v], min(lvl[v] + k, n));
  142.         cout << last << " ";
  143.     }
  144.     cout << endl;
  145.     return 0;
  146. }
RAW Paste Data