• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

【题解】Ynoi 2008 rdCcot

开发技术 开发技术 3小时前 3次浏览

常见的套路是,对于要统计的连通块,钦定一个关键点,统计关键点的数量。

考虑某个 C-块 的最浅的点,由于这样的最浅的点有多个,考虑怎么钦定一个点作为关键点。事实上,对于这些点可以考虑按照某个顺序排序,只有当一个点前面没有与其 C-联通 的点时,才能被钦定为关键点。

同时考虑更深一些的点,这些点如果跟更浅的那些点满足 C-联通,那么就没有被钦定为关键点的可能。所以,将所有的点以深度为第一关键字排序,然后通过检查一个点之前有没有和该点 C-联通 的点来判断该点是否能被钦定为关键点,这样的策略是恰好满足要求的。

那么可以注意到一个点能做贡献,当且仅当之前跟其 C-联通 的点不在区间内,现在的问题就是找前驱后继,考虑点分治,将所有点按照排序后的顺序加入,以下标为第一关键字,维护区间到分治中心距离最小值,二分查询即可。(注意到同一子树再在分治中心计算时,距离不会更小,所以不影响答案)。

本题卡常,注意实现,这里给出部分代码。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair <int, int> pii;

#define fi first
#define se second
#define rez resize
#define pb push_back
#define mkp make_pair

#define Lep(i, l, r) for (int i = l; i < r; ++ i)
#define Rep(i, r, l) for (int i = r; i > l; -- i)
#define lep(i, l, r) for (int i = l; i <= r; ++ i)
#define rep(i, r, l) for (int i = r; i >= l; -- i)

namespace io {
    const int SIZE = (1 << 25) + 1;
    char ibuf[SIZE], *iS, *iT;
    char obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c, qu[16];
    int f, qr;
    
    #define gc() (iS == iT ? (iT = (iS = ibuf) + fread (ibuf, 1, SIZE, stdin), (iS == iT ? EOF : *iS ++)) : *iS ++)
    
    inline void flush () {
        fwrite (obuf, 1, oS - obuf, stdout);
        oS = obuf;
    }
    inline void putc (char x) {
        *oS ++ = x;
        if (oS == oT) flush ();
    }
    template <class I> inline void IN (I &x) {
        for (f = 1, c = gc(); c < '0' || c > '9'; c = gc()) if (c == '-') f = -1;
        for (x = 0; c <= '9' && c >= '0'; c = gc()) x = x * 10 + (c & 15); 
        x = f == -1 ? -x : x;
    }
    template <class I> inline void print (I x) {
        if (! x) putc ('0'); if (x < 0) putc ('-'), x = -x;
        while (x) qu[ ++ qr] = x % 10 + '0',  x /= 10;
        while (qr) putc (qu[qr -- ]);
    }
    struct Flusher_ {~Flusher_(){flush();}}io_flusher_;
}
using io :: IN;
using io :: putc;
using io :: print;

template <class T> inline void chkmin (T & x, T y) { if (x > y) x = y; }
template <class T> inline void chkmax (T & x, T y) { if (x < y) x = y; }

const int N = 3e5 + 5;

int n, m, C, L[N], R[N], rk[N], id[N];

int tot, head[N];
struct edge { int nxt, to; } G[N << 1];
inline void addedge (int u, int v) {
    G[ ++ tot] = (edge) {head[u], v}, head[u] = tot;
    G[ ++ tot] = (edge) {head[v], u}, head[v] = tot;
}

struct fhq_treap {// {{{ fhq treap
    int rt, cnt;
    struct node { int lc, rc, mi, id, siz, rnd, val; } t[N];

    inline int newnode (int id, int val) {
        ++ cnt, t[cnt].mi = t[cnt].val = val, t[cnt].siz = 1, t[cnt].rnd = rand (), t[cnt].id = id;
        return cnt;
    }
    inline void pushup (int x) {
        t[x].mi = min (t[x].val, min (t[t[x].lc].mi, t[t[x].rc].mi));
        t[x].siz = t[t[x].lc].siz + t[t[x].rc].siz + 1;
    }
    inline void clear () {
        rt = 0; while (cnt) t[cnt].lc = t[cnt].rc = 0, -- cnt;
    }

    void split (int now, int k, int &x, int &y) {
        if (! now) return x = y = 0, void ();
        if (t[now].id <= k) x = now, split (t[x].rc, k, t[x].rc, y), pushup (x);
        else y = now, split (t[y].lc, k, x, t[y].lc), pushup (y);
    }
    int merge (int x, int y) {
        if (! x || ! y) return x | y;
        if (t[x].rnd <= t[y].rnd) return t[x].rc = merge (t[x].rc, y), pushup (x), x;
        else return t[y].lc = merge (x, t[y].lc), pushup (y), y;
    }

    inline void calc (const int &id, const int &val) {
        int lim = C - val, _tx, _ty, _tz;
        split (rt, id, _tx, _ty);

        _tz = _tx; while (_tz && t[_tz].mi <= lim) {
            if (t[_tz].val <= lim) chkmax (L[id], t[_tz].id), _tz = t[_tz].rc;
            else _tz = (t[_tz].rc && t[t[_tz].rc].mi <= lim) ? t[_tz].rc : t[_tz].lc;
        }
        _tz = _ty; while (_tz && t[_tz].mi <= lim) {
            if (t[_tz].val <= lim) chkmin (R[id], t[_tz].id), _tz = t[_tz].lc;
            else _tz = (t[_tz].lc && t[t[_tz].lc].mi <= lim) ? t[_tz].lc : t[_tz].rc;
        }
        rt = merge (merge (_tx, newnode (id, val)), _ty);
    }
} t; // }}}

// {{{ tree divide

bool vis[N];
int rt, all, len, mxp[N], dep[N], siz[N], pot[N];

void init (int u, int pre) {
    dep[u] = dep[pre] + 1;
    for (int v, i = head[u]; i; i = G[i].nxt) if (v = G[i].to, v != pre) init (v, u);
}
void getsiz (int u, int pre) {
    siz[u] = 1;
    for (int v, i = head[u]; i; i = G[i].nxt) if (! vis[v = G[i].to] && v != pre) getsiz (v, u), siz[u] += siz[v];
}
void getrt (int u, int pre) {
    mxp[u] = all - siz[u];
    for (int v, i = head[u]; i; i = G[i].nxt) if (! vis[v = G[i].to] && v != pre) getrt (v, u), chkmax (mxp[u], siz[v]);
    if (mxp[u] < mxp[0]) rt = u, mxp[0] = mxp[u];
}

void getpot (int u, int pre) {
    pot[ ++ len] = u, dep[u] = dep[pre] + 1;
    for (int v, i = head[u]; i; i = G[i].nxt) if (! vis[v = G[i].to] && v != pre) getpot (v, u);
}

void divide (int u) {
    vis[u] = true, pot[len = 1] = u, dep[u] = 0;
    for (int v, i = head[u]; i; i = G[i].nxt) if (! vis[v = G[i].to]) getpot (v, u);
    sort (pot + 1, pot + 1 + len, [&](const int x, const int y) { return rk[x] < rk[y]; });

    lep (i, 1, len) t.calc (pot[i], dep[pot[i]]);
    t.clear ();

    for (int v, i = head[u]; i; i = G[i].nxt) if (! vis[v = G[i].to])
        getsiz (v, u), all = siz[v], mxp[0] = all + 1, getrt (v, u), divide (rt);
}

// }}}

int tu, tc[N], ans[N << 1];
vector <pii> add[N], del[N], qsta[N];

inline int lowbit (int x) { return x & (-x); }
inline void modify (int x, int y) { while (x <= n) tc[x] += y, x += lowbit (x); }
inline int query (int x) { int res = 0; while (x) res += tc[x], x -= lowbit (x); return res; }

int main () {
    srand (time (0));

    IN (n), IN (m), IN (C);
    lep (i, 2, n) IN (tu), addedge (i, tu);

    lep (i, 1, n) L[i] = 0, R[i] = n + 1, id[i] = i;
    init (1, 0), sort (id + 1, id + 1 + n, [&](const int x, const int y) {
        return dep[x] == dep[y] ? x < y : dep[x] < dep[y];
    });
    lep (i, 1, n) rk[id[i]] = i;

    t.t[0].mi = t.t[0].val = n + 1;
    lep (i, 1, n) dep[i] = 0;
    getsiz (1, 0), all = siz[1], mxp[0] = all + 1, getrt (1, 0), divide (rt);
    lep (i, 1, n) ++ L[i], -- R[i];

    for (int i = 1, l, r; i <= m; ++ i) IN (l), IN (r), qsta[r].pb (mkp (l, i));
    lep (i, 1, n) add[i].pb (mkp (L[i], i)), del[R[i] + 1].pb (mkp (L[i], i));

    lep (i, 1, n) {
        for (auto now : add[i]) modify (now.fi, 1), modify (now.se + 1, -1);
        for (auto now : del[i]) modify (now.fi, -1), modify (now.se + 1, 1);
        for (auto now : qsta[i]) ans[now.se] = query (now.fi);
    }
    lep (i, 1, m) print (ans[i]), putc ('n');
    return 0;
}

程序员灯塔
转载请注明原文链接:【题解】Ynoi 2008 rdCcot
喜欢 (0)