题解：P5346 【XR-1】柯南家族

· · 题解

关于一个名柯粉刷到这题的心情：o( ￣ ︶ ￣ )o这题不会做也会做，不然心里崩塌

废话不多说了，正题开始

求出每一个点的排名后,祖先链上建主席树,子树里就线段树合并就完事了，结果尴尬的事情就这么水灵灵的发生了，发现自己不会写代码 o(╥﹏╥)o

其实写一个替罪羊树就肥肠非常方便和煎蛋简单了虽然代码短不到哪里去

就是先用 替罪羊树+赋予节点权值把节点排个序,然后再用线段树就可以得出answer(暴算)简单粗暴，思维含量不高

复杂度 O(nlogn) ，经过我“周密”的计算(事实上是去试试了亿下)这不会超时!

接下来就是万众瞩目的代码了↓

头文件和主函数就自己写吧，我懒得写了☺

inline int gi()
{
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    int sum = 0;
    while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
    return sum;
}

const int maxn = 500005;
const double alpha = 0.7;

int n, q, fa[maxn], c[maxn];

int rt, lch[maxn], rch[maxn], siz[maxn], cnt, tmp[maxn];
double w[maxn];

void dfs(int u)
{
    if (lch[u]) dfs(lch[u]);
    tmp[++cnt] = u;
    if (rch[u]) dfs(rch[u]);
}

void build(int &u, int l, int r, double wl, double wr)
{
    int mid = (l + r) >> 1;
    u = tmp[mid]; w[u] = (wl + wr) / 2;
    if (l < mid) build(lch[u], l, mid - 1, wl, w[u]); else lch[u] = 0;
    if (mid < r) build(rch[u], mid + 1, r, w[u], wr); else rch[u] = 0;
    siz[u] = 1 + siz[lch[u]] + siz[rch[u]];
}

void rebuild(int &u, double l, double r) {cnt = 0; dfs(u); build(u, 1, cnt, l, r);}

inline bool cmp(int a, int b)
{
    if (c[a] != c[b]) return c[a] > c[b];
    else if (fa[a] && fa[b] && fa[a] != fa[b]) return w[fa[a]] < w[fa[b]];
    else return a > b;
}

void insert(int &u, int x, double l, double r, bool f)
{
    if (!u) return u = x, siz[u] = 1, w[x] = (l + r) / 2, void();
    ++siz[u];
    bool flg = 0;
    if (cmp(x, u)) {
        flg |= alpha * (siz[lch[u]] + 1) > siz[rch[u]];
        insert(lch[u], x, l, w[u], flg);
    } else {
        flg |= alpha * (siz[rch[u]] + 1) > siz[lch[u]];
        insert(rch[u], x, w[u], r, flg);
    }
    if (flg && !f) rebuild(u, l, r);
}

struct edge
{
    int to, next;
} e[maxn];
int h[maxn], rk[maxn], dfn[maxn], low[maxn], T, ecnt;

inline void add(int u, int v) {e[++ecnt] = (edge) {v, h[u]}; h[u] = ecnt;}

struct node
{
    int lch, rch, siz;
} s[maxn * 60];
int tot, rt1[maxn], rt2[maxn];

void modify(int &x, int l, int r, int p)
{
    ++tot; s[tot] = s[x]; ++s[x = tot].siz;
    if (l == r) return ;
    int mid = (l + r) >> 1;
    if (p <= mid) modify(s[x].lch, l, mid, p);
    else modify(s[x].rch, mid + 1, r, p);
}

int query(int x, int y, int l, int r, int k)
{
    if (l == r) return tmp[l];
    int mid = (l + r) >> 1;
    if (k > s[s[y].lch].siz - s[s[x].lch].siz) return query(s[x].rch, s[y].rch, mid + 1, r, k - (s[s[y].lch].siz - s[s[x].lch].siz));
    else return query(s[x].lch, s[y].lch, l, mid, k);
}

void t_dfs(int u)
{
    dfn[u] = ++T;
    rt1[u] = rt1[fa[u]]; modify(rt1[u], 1, n, rk[u]);
    rt2[T] = rt2[T - 1]; modify(rt2[T], 1, n, rk[u]);
    for (int i = h[u], v; v = e[i].to, i; i = e[i].next)
        if (v != fa[u]) t_dfs(v);
    low[u] = T;
}

彩蛋

大家有没有发现一件十分重大的事：

这个题目发布时间是2019-05-04，这个日期看似正常实则也很正常是一个对于本题主人公的一个特殊日子——生日！！

虽然我在2024-12-29才刷到，但是还是要祝福他生日快乐啦

另外，2024对于《名侦探柯南》也是一个重大年份，是名柯连载30周年纪念日！而我们的南哥还是7(17)岁

【完结撒花】