题解 CF1062E 【Company】

ywy_c_asm · 2019-05-23 23:29:24 · 题解

md真降智了……删dfn最小或最大的点就行了……

那我就来个数据结构学傻了的代码6个多K的辣鸡做法吧……

首先，我们可以知道[l,r]的LCA，这个由于LCA是可合并的拿个线段树可以维护（需要用O(1)LCA）。如果这个LCA\in [l,r]那肯定删的就是LCA，否则假设我们知道[l,r]构成的极大连通块（和虚树的区别就是包含所有经过的点）T，考虑LCA在T上的儿子，如果它有多于2个儿子那显然不管删哪个点得到的都还是这个LCA。否则的话，它一定有两个儿子a和b，考虑它们的子树，那肯定是要删子树内只有一个点在[l,r]内的那个点才会使答案改变，讨论一下即可。

考虑上述操作怎么实现，首先我们可以用线段树合并知道子树内[l,r]的点的信息，并且如果只有一个点的话可以线段树上二分找到这个点。然后考虑怎么处理LCA在T上的儿子，我们肯定不能每次暴力扫一遍儿子，这会被菊花卡。然而，我们知道如果把树树链剖分一下的话一个点最多只有一个重儿子（这个可以直接特判），而轻儿子是可以支持动态维护的，那么就有了一个做法：离线把询问存在右端点上，然后扫描线，我们希望知道LCA有哪些轻儿子满足在子树里存在[l,r]内的点，那么我们令每个轻儿子的点权是子树内<=当前右端点的最大值（这样如果>=l就说明子树内存在[l,r]的点），我们每扫到一个r就跳链把所有重链链顶的点权改成r即可，然后我们只要在LCA处维护点权最大的2个或3个即可，这可以在每个点开个支持修改的可删堆维护轻儿子。然后就O(n\log^2n)做完了，瓶颈在于链剖维护轻儿子。

上代码~（格式化后有10K……）

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define N 100011
#define ls(_o) (_o << 1)
#define rs(_o) ((_o << 1) | 1)
using namespace std;
namespace ywy {
    inline int get() {
        int n = 0;
        char c;
        while ((c = getchar()) || 23333) {
            if (c >= '0' && c <= '9')
                break;
            if (c == '-')
                goto s;
        }
        n = c - '0';
        while ((c = getchar()) || 23333) {
            if (c >= '0' && c <= '9')
                n = n * 10 + c - '0';
            else
                return (n);
        }
    s:
        while ((c = getchar()) || 23333) {
            if (c >= '0' && c <= '9')
                n = n * 10 - c + '0';
            else
                return (n);
        }
    }
    typedef struct _b {
        int dest;
        int nxt;
    } bian;
    bian memchi[1000001];
    int gn = 1, heads[N], dfn[N], fan[N], size[N], zhongson[N], st[N * 2][18], lg[N * 2], gdfn = 1;
    inline void add(int s, int t) {
        memchi[gn].dest = t;
        memchi[gn].nxt = heads[s];
        heads[s] = gn;
        gn++;
    }
    int early[N], late[N], top[N], gstp = 1, rt[N], lef[10000001], rgh[10000001], data[10000001], gseg = 1;
    inline int lca(int a, int b) {
        if (!(a && b))
            return (a | b);
        if (dfn[a] > dfn[b])
            swap(a, b);
        a = early[a];
        b = late[b];
        int g = lg[b - a + 1];
        return (fan[min(st[a][g], st[b - (1 << g) + 1][g])]);
    }
    int lcas[1000001];
    void build(int l, int r, int tree) {
        if (l == r) {
            lcas[tree] = l;
            return;
        }
        int mid = (l + r) >> 1;
        build(l, mid, ls(tree));
        build(mid + 1, r, rs(tree));
        lcas[tree] = lca(lcas[ls(tree)], lcas[rs(tree)]);
    }
    int query(int rl, int rr, int l, int r, int tree) {
        if (rl > rr)
            return (0);
        if (rl == l && rr == r)
            return (lcas[tree]);
        int mid = (l + r) >> 1;
        if (rl > mid)
            return (query(rl, rr, mid + 1, r, rs(tree)));
        if (rr <= mid)
            return (query(rl, rr, l, mid, ls(tree)));
        return (lca(query(rl, mid, l, mid, ls(tree)), query(mid + 1, rr, mid + 1, r, rs(tree))));
    }
    void insert(int l, int r, int &tree, int pt) {
        if (!tree)
            tree = gseg, gseg++;
        data[tree]++;
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        if (pt <= mid)
            insert(l, mid, lef[tree], pt);
        else
            insert(mid + 1, r, rgh[tree], pt);
    }
    int qdat(int rl, int rr, int l, int r, int tree) {
        if (!data[tree])
            return (0);
        if (rl == l && rr == r)
            return (data[tree]);
        int mid = (l + r) >> 1;
        if (rl > mid)
            return (qdat(rl, rr, mid + 1, r, rgh[tree]));
        if (rr <= mid)
            return (qdat(rl, rr, l, mid, lef[tree]));
        return (qdat(rl, mid, l, mid, lef[tree]) + qdat(mid + 1, rr, mid + 1, r, rgh[tree]));
    }
    int united(int a, int b) {
        if (!(a && b))
            return (a | b);
        int me = gseg;
        gseg++;
        data[me] = data[a] + data[b];
        lef[me] = united(lef[a], lef[b]);
        rgh[me] = united(rgh[a], rgh[b]);
        return (me);
    }
    int qfirst(int rl, int rr, int l, int r, int tree) {
        if (!data[tree])
            return (0);
        if (l == r)
            return (l);
        int mid = (l + r) >> 1;
        if (rl == l && rr == r) {
            if (data[lef[tree]])
                return (qfirst(l, mid, l, mid, lef[tree]));
            return (qfirst(mid + 1, r, mid + 1, r, rgh[tree]));
        }
        if (rl > mid)
            return (qfirst(rl, rr, mid + 1, r, rgh[tree]));
        if (rr <= mid)
            return (qfirst(rl, rr, l, mid, lef[tree]));
        int cjr = qfirst(rl, mid, l, mid, lef[tree]);
        if (cjr)
            return (cjr);
        return (qfirst(mid + 1, rr, mid + 1, r, rgh[tree]));
    }
    typedef struct _p {
        int a;
        int b;
        _p(int i, int j) {
            a = i;
            b = j;
        }
        friend bool operator<(const _p &a, const _p &b) {
            if (a.b != b.b)
                return (a.b < b.b);
            return (a.a < b.a);
        }
        friend bool operator==(const _p &a, const _p &b) { return (a.a == b.a && a.b == b.b); }
    } pair;
    typedef struct _heap {
        priority_queue<pair> me, del;
        inline void wh() {
            while (!me.empty() && !del.empty() && me.top() == del.top()) me.pop(), del.pop();
        }
        inline void push(pair x) { me.push(x); }
        inline int size() { return (me.size() - del.size()); }
        inline pair top() {
            wh();
            return (me.top());
        }
        inline void erase(pair x) { del.push(x); }
        inline void pop() {
            wh();
            me.pop();
        }
    } heap;
    heap chs[100001];
    int n;
    int deep[N];
    int lst[N], fa[N];
    void dfs(int pt, int baba) {
        size[pt] = 1;
        int mx = 0, best = 0;
        for (register int i = heads[pt]; i; i = memchi[i].nxt) {
            if (memchi[i].dest == baba)
                continue;
            deep[memchi[i].dest] = deep[pt] + 1;
            dfs(memchi[i].dest, pt);
            size[pt] += size[memchi[i].dest];
            rt[pt] = united(rt[pt], rt[memchi[i].dest]);
            if (size[memchi[i].dest] > mx)
                mx = size[memchi[i].dest], best = memchi[i].dest;
        }
        insert(1, n, rt[pt], pt);
        top[pt] = pt;
        zhongson[pt] = best;
        lst[pt] = -1;
    }
    int anspt[N], anss[N];
    void efs(int pt, int baba) {
        if (zhongson[pt])
            top[zhongson[pt]] = top[pt], efs(zhongson[pt], pt);
        for (register int i = heads[pt]; i; i = memchi[i].nxt) {
            if (memchi[i].dest == baba || zhongson[pt] == memchi[i].dest)
                continue;
            efs(memchi[i].dest, pt);
        }
    }
    vector<pair> vec[N];  // a->l,b->id
    void ffs(int pt, int baba) {
        dfn[pt] = gdfn;
        fan[gdfn] = pt;
        gdfn++;
        st[gstp][0] = dfn[pt];
        gstp++;
        early[pt] = late[pt] = gstp - 1;
        for (register int i = heads[pt]; i; i = memchi[i].nxt) {
            if (memchi[i].dest == baba)
                continue;
            ffs(memchi[i].dest, pt);
            st[gstp][0] = dfn[pt];
            late[pt] = gstp;
            gstp++;
        }
    }
    inline int calc(int l, int r, int x) { return (lca(query(l, x - 1, 1, n, 1), query(x + 1, r, 1, n, 1))); }
    vector<int> tmp;
    inline void clear(vector<int> &v) {
        vector<int> ff;
        v = ff;
    }
    void ywymain() {
        n = get();
        int q = get();
        for (register int i = 2; i <= n; i++) add(fa[i] = get(), i);
        ffs(1, 0);
        gstp--;
        lg[0] = -1;
        for (register int i = 1; i <= gstp; i++) lg[i] = lg[i - 1] + (i == (i & -i));
        for (register int i = 1; i <= lg[gstp]; i++) {
            for (register int j = 1; j <= gstp - (1 << i) + 1; j++)
                st[j][i] = min(st[j][i - 1], st[j + (1 << (i - 1))][i - 1]);
        }
        build(1, n, 1);
        dfs(1, 0);
        efs(1, 0);
        for (register int i = 1; i <= q; i++) {
            int l = get(), r = get();
            vec[r].push_back(_p(l, i));
        }
        for (register int i = 1; i <= n; i++) {
            int cur = top[i];
            while (fa[cur]) {
                if (lst[cur] != -1)
                    chs[fa[cur]].erase(_p(cur, lst[cur]));
                chs[fa[cur]].push(_p(cur, lst[cur] = i));
                cur = top[fa[cur]];
            }
            for (register int j = 0; j < vec[i].size(); j++) {
                int ance = query(vec[i][j].a, i, 1, n, 1);
                if (ance >= vec[i][j].a && ance <= i) {
                    anspt[vec[i][j].b] = ance;
                    anss[vec[i][j].b] = deep[calc(vec[i][j].a, i, ance)];
                    continue;
                }
                clear(tmp);
                if (zhongson[ance]) {
                    if (qdat(vec[i][j].a, i, 1, n, rt[zhongson[ance]]))
                        tmp.push_back(zhongson[ance]);
                }
                if (chs[ance].size() >= 1) {
                    pair cjr = chs[ance].top();
                    chs[ance].pop();
                    if (cjr.b >= vec[i][j].a) {
                        tmp.push_back(cjr.a);
                        if (chs[ance].size() >= 1) {
                            pair a = chs[ance].top();
                            chs[ance].pop();
                            if (a.b >= vec[i][j].a) {
                                tmp.push_back(a.a);
                                if (chs[ance].size() >= 1) {
                                    pair b = chs[ance].top();
                                    chs[ance].pop();
                                    if (b.b >= vec[i][j].a) {
                                        tmp.push_back(b.a);
                                    }
                                    chs[ance].push(b);
                                }
                            }
                            chs[ance].push(a);
                        }
                    }
                    chs[ance].push(cjr);
                }
                if (tmp.size() >= 3) {
                    anss[vec[i][j].b] = deep[ance];
                    anspt[vec[i][j].b] = i;
                    continue;
                }
                anspt[vec[i][j].b] = i;
                anss[vec[i][j].b] = deep[ance];
                for (register int k = 0; k < 2; k++) {
                    if (qdat(vec[i][j].a, i, 1, n, rt[tmp[k]]) == 1) {
                        int best = qfirst(vec[i][j].a, i, 1, n, rt[tmp[k]]),
                            res = deep[calc(vec[i][j].a, i, best)];
                        if (res > anss[vec[i][j].b])
                            anss[vec[i][j].b] = res, anspt[vec[i][j].b] = best;
                    }
                }
            }
        }
        for (register int i = 1; i <= q; i++) printf("%d %d\n", anspt[i], anss[i]);
    }
}
int main() {
    ywy::ywymain();
    return (0);
}