Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define ll long long
- #define all(x) (x).begin(), (x).end()
- #define rall(x) (x).rbegin(), (x).rend()
- #define watch(x) cout << (#x) << " : " << x << '\n'
- #define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
- using namespace std;
- struct item {
- int min_val;
- int max_val;
- int min_id;
- int max_id;
- void init(int v, int pos) {
- min_val = max_val = v;
- min_id = max_id = pos;
- }
- };
- item merge(item a, item b) {
- item res;
- if (a.max_val > b.max_val)
- res.max_val = a.max_val, res.max_id = a.max_id;
- else
- res.max_val = b.max_val, res.max_id = b.max_id;
- if (a.min_val < b.min_val)
- res.min_val = a.min_val, res.min_id = a.min_id;
- else
- res.min_val = b.min_val, res.min_id = b.min_id;
- return res;
- }
- struct segtree {
- vector < item > t;
- int base, N;
- void init(vector<int>& a) {
- int n = (int)a.size();
- t.resize(4 * n);
- build(a, 1, 0, n - 1);
- N = n;
- }
- void build(vector<int>& a, int v, int tl, int tr) {
- if (tl == tr) {
- t[v].init(a[tl], tl);
- return;
- }
- int tm = (tl + tr) >> 1;
- build(a, v << 1, tl, tm);
- build(a, v << 1 | 1, tm + 1, tr);
- t[v] = merge(t[v << 1], t[v << 1 | 1]);
- }
- item get(int l, int r, int v, int tl, int tr) {
- if (tl > r || tr < l)
- return item{(int)2e9, (int)-2e9, -1, -1};
- if (l <= tl && tr <= r)
- return t[v];
- int tm = (tl + tr) >> 1;
- return merge(get(l, r, v << 1, tl, tm),
- get(l, r, v << 1 | 1, tm + 1, tr));
- }
- item get(int l, int r) {
- if (l > r)
- return item{(int)2e9, (int)-2e9, -1, -1};
- return get(l, r, 1, 0, N - 1);
- }
- };
- const int N = 1e5 + 128;
- const int LOG = 20;
- int lift[N][LOG];
- int depth[N];
- int tin[N], tout[N];
- vector <int> g[N];
- int n, q;
- int timer;
- vector <int> order;
- void dfs(int v, int d = 0, int p = 1) {
- order.push_back(v);
- tin[v] = timer++;
- depth[v] = d;
- lift[v][0] = p;
- for (int b = 1; b < LOG; b++)
- lift[v][b] = lift[lift[v][b-1]][b-1];
- for (auto to : g[v])
- if (to != p)
- dfs(to, d + 1, v);
- order.push_back(v);
- tout[v] = timer++;
- }
- void solve() {
- cin >> n >> q;
- for (int i = 2; i <= n; i++) {
- int x;
- cin >> x;
- g[i].push_back(x);
- g[x].push_back(i);
- }
- dfs(1);
- segtree tmin, tmax, thei;
- vector <int> ttin, ttout;
- for (int i = 0; i < n; i++)
- ttin.push_back(tin[i + 1]), ttout.push_back(tout[i + 1]);
- tmin.init(ttin);
- tmax.init(ttout);
- vector<int> heii;
- for (auto c : order)
- heii.push_back(depth[c]);
- thei.init(heii);
- while (q--) {
- int l, r;
- cin >> l >> r;
- l--; r--;
- auto t_min = tmin.get(l, r);
- auto t_max = tmax.get(l, r);
- int delete_left = t_min.min_id;
- int delete_right = t_max.max_id;
- int delete_ans = -1;
- int ans = -1;
- auto t_min_without_deleted_left = merge(tmin.get(l, delete_left - 1), tmin.get(delete_left + 1, r));
- auto t_max_without_deleted_right = merge(tmax.get(l, delete_right - 1), tmax.get(delete_right + 1, r));
- int without_left_ans, without_right_ans;
- if (t_min_without_deleted_left.min_val + 1 >= t_min_without_deleted_left.max_val)
- without_left_ans = thei.get(t_min_without_deleted_left.min_val, t_min_without_deleted_left.max_val).min_val + 1;
- else
- without_left_ans = thei.get(t_min_without_deleted_left.min_val + 1, t_min_without_deleted_left.max_val - 1).min_val;
- if (t_max_without_deleted_right.min_val + 1 >= t_max_without_deleted_right.max_val)
- without_right_ans = thei.get(t_max_without_deleted_right.min_val, t_max_without_deleted_right.max_val).min_val + 1;
- else
- without_right_ans = thei.get(t_max_without_deleted_right.min_val + 1, t_max_without_deleted_right.max_val - 1).min_val;
- if (ans < without_left_ans)
- ans = without_left_ans, delete_ans = delete_left;
- if (ans < without_right_ans)
- ans = without_right_ans, delete_ans = delete_right;
- cout << delete_ans + 1 << ' ' << ans - 1 << '\n';
- }
- }
- main() {
- boost;
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement