[Luogu] [HNOI2015]接水果
本文最后更新于 89 天前,其中的信息可能已经有所发展或是发生改变。

一道树上问题转dfs序后,利用整体二分转化的数点问题。

Before the Beginning

转载请将本段放在文章开头显眼处,如有二次创作请标明。
原文链接:https://www.codein.icu/lp3242/

题意

盘子和水果都是路径。盘子有权值,一个盘子能接住水果,要求盘子的路径是水果的子路径。
问某个水果的权值第 $k_i$ 小的盘子的权值。

题解

求第 $k$ 小,可以考虑使用整体二分,转化为判定性问题。
二分权值,将 $\le mid$ 的路径全部计入贡献,对于每个水果,求出此时它的子路径的数量,如果更多说明权值可以更小,否则权值更大。

发现求子路径很不好处理。于是点开题解,发现了一种神奇的处理方法。
子路径可以转化为 dfs 序的问题。接下来开始YY:

分成两种情况讨论:原路径链与非链。
对于一条路径 $a \to b$,其中 $lca(a,b) = a$,则称之为链,否则为非链。

对于一条链路径,如果它是 $u \to v$ 的子路径,那么 $u$ 点在 $a$ 的包含 $a$ 点的父亲子树中,$v$ 点在 $b$ 点的子树中。

对于一条非链路径,如果它是 $u \to v$ 的子路径,那么 $u$ 点在 $a$ 的子树中,$v$ 点在 $b$ 点的子树中。
定义 $st(u)$ 为 $u$ 点进入时的 dfs 序,$ed(u)$ 为 $u$ 点退出时的 dfs 序,那么它的子树 dfs 序就是 $[st(u),ed(u)]$.
可以发现,$a$ 点的父亲子树,需要在 $a\to b$ 上从 $a$ 向下走一步得到点 $z$,然后挖去点 $z$ 的子树,就可以得到 $a$ 的父亲子树。
用树剖往上跳。

对于链路径:

$$\begin{aligned} & dfn[u] \notin [st(z),ed(z)] \\ & dfn[v] \in [st(b),ed(b)] \end{aligned}$$
拆开,有:

$$\begin{aligned} & dfn[u] \in [1,st(z) – 1] \\ & dfn[v] \in [st(b),ed(b)] \end{aligned}$$
另一个矩形:

$$\begin{aligned} & dfn[u] \in [st(b),ed(b)] \\ & dfn[v] \in [ed(z) + 1,n] \end{aligned}$$
这里需要注意,由于定义 $dfn[u] < dfn[v]$,而有 $ed(z) > ed(b)$,因此需要旋转矩形。

对于非链路径:

$$\begin{aligned} & dfn[u] \in [st(a),ed(a)] \\ & dfn[v] \in [st(b),ed(b)] \end{aligned}$$
那么将水果看成一个点,将盘子看成矩形,相当于询问一个点被多少个矩形覆盖。
扫描线就可以维护了。

代码

细节比较恶心。

#include <cstdio>
#include <algorithm>
#include <ctype.h>
const int bufSize = 1e6;
inline char nc()
{
    #ifdef DEBUG
    return getchar();
    #endif
    static char buf[bufSize], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, bufSize, stdin), p1 == p2) ? EOF : *p1++;
}
template<typename T>
inline T read(T &r)
{
    static char c;
    static int flag;
    flag = 1, r = 0;
    for (c = nc(); !isdigit(c); c = nc()) if (c == '-') flag = -1;
    for (; isdigit(c); c = nc()) r = r * 10 + c - 48;
    return r *= flag;
}
const int maxn = 2e5;
struct node
{
    int to, next;
} E[maxn];
int head[maxn];
inline void add(const int& x, const int& y)
{
    static int tot = 0;
    E[++tot].next = head[x], E[tot].to = y, head[x] = tot;
}
int n, m, q, dep[maxn], size[maxn], son[maxn], fa[maxn], top[maxn], dfn[maxn], ed[maxn], id[maxn],ind, cnt, ans[maxn];
void dfs1(int u)
{
    size[u] = 1;
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (v == fa[u]) continue;
        fa[v] = u, dep[v] = dep[u] + 1, dfs1(v), size[u] += size[v];
        if (size[v] > size[son[u]]) son[u] = v;
    }
}
void dfs2(int u)
{
    id[dfn[u] = ++ind] = u;
    if (!son[u]) return (void)(ed[u] = ind);
    top[son[u]] = top[u], dfs2(son[u]);
    for (int p = head[u]; p; p = E[p].next)
    {
        int v = E[p].to;
        if (v == fa[u] || v == son[u]) continue;
        top[v] = v, dfs2(v);
    }
    ed[u] = ind;
}
inline int getz(int x, int y)
{
    int pre = 0;
    while (top[x] != top[y]) pre = y, y = fa[top[y]];
    if (dfn[x] + 1 <= dfn[y]) return id[dfn[x] + 1];  //heavy son
    else return pre;
}
struct query
{
    int x, type, l, r, val, id;
} Q[maxn], q1[maxn], q2[maxn];
bool cmp(const query& a, const query& b)
{
    if (a.x != b.x) return a.x < b.x;
    return a.type < b.type;
}
namespace Bit
{
int sum[maxn], vis[maxn], tim;
inline void clear() { ++tim; }
inline void check(int x) { if (vis[x] != tim) sum[x] = 0, vis[x] = tim; }
inline void add(int x, int k) { for (; x <= n; x += x & -x) check(x), sum[x] += k; }
inline int ask(int x)
{
    int res = 0;
    for (; x > 0; x -= x & -x) check(x), res += sum[x];
    return res;
}
inline void addrange(int l, int r, int k) { if (l <= r) add(l, k), add(r + 1, -k); }
}  // namespace Bit
int H[maxn], hcnt;
void solve(int l, int r, int L, int R)
{
    if(L > R) return;
    if(l == r)
    {
        for (int i = L; i <= R; ++i) if (Q[i].type == 3) ans[Q[i].id] = l;
        return;
    }
    bool flag = 0;
    for (int i = L; !flag && i <= R; ++i) flag |= (Q[i].type == 3);
    if (!flag) return;
    int mid = l + r >> 1, cnt1 = 0, cnt2 = 0;
    for (int i = L; i <= R; ++i)
    {
        if(Q[i].type <= 2)
        {
            int t = (Q[i].type == 1 ? 1 : -1);
            if (Q[i].val <= H[mid]) Bit::add(Q[i].l, t), Bit::add(Q[i].r + 1, -t), q1[++cnt1] = Q[i];
            else q2[++cnt2] = Q[i];
        }
        else
        {
            int num = Bit::ask(Q[i].l);
            if (num >= Q[i].val) q1[++cnt1] = Q[i];
            else Q[i].val -= num, q2[++cnt2] = Q[i];
        }
    }
    Bit::clear();
    for (int i = 1; i <= cnt1; ++i) Q[L + i - 1] = q1[i];
    for (int i = 1; i <= cnt2; ++i) Q[L + cnt1 + i - 1] = q2[i];
    solve(l, mid, L, L + cnt1 - 1), solve(mid + 1, r, L + cnt1, R);
}
int main()
{
    read(n), read(m), read(q);
    for (int i = 1, a, b; i < n; ++i) read(a), read(b), add(a, b), add(b, a);
    dep[1] = 1, dfs1(1), top[1] = 1, dfs2(1);
    for (int i = 1, u, v, k; i <= m; ++i) 
    {
        read(u), read(v), read(k), H[++hcnt] = k;
        if (dfn[u] > dfn[v]) std::swap(u, v);
        if(dfn[v] >= dfn[u] && ed[v] <= ed[u])
        {
            int z = getz(u, v);
            if(dfn[z] > 1)
            {
                Q[++cnt].type = 1, Q[cnt].x = 1, Q[cnt].l = dfn[v], Q[cnt].r = ed[v], Q[cnt].val = k;
                Q[++cnt].type = 2, Q[cnt].x = dfn[z], Q[cnt].l = dfn[v], Q[cnt].r = ed[v], Q[cnt].val = k;
            }
            if(ed[z] < n)
            {
                Q[++cnt].type = 1, Q[cnt].x = dfn[v], Q[cnt].l = ed[z] + 1, Q[cnt].r = n, Q[cnt].val = k;
                Q[++cnt].type = 2, Q[cnt].x = ed[v] + 1, Q[cnt].l = ed[z] + 1, Q[cnt].r = n, Q[cnt].val = k;
            }
        }
        else
        {
            Q[++cnt].type = 1, Q[cnt].x = dfn[u], Q[cnt].l = dfn[v], Q[cnt].r = ed[v], Q[cnt].val = k;
            Q[++cnt].type = 2, Q[cnt].x = ed[u] + 1, Q[cnt].l = dfn[v], Q[cnt].r = ed[v], Q[cnt].val = k;
        }
    }
    for (int i = 1, u, v, k; i <= q; ++i)
    {
        read(u), read(v), read(k);
        if (dfn[u] > dfn[v]) std::swap(u, v);
        Q[++cnt].type = 3, Q[cnt].x = dfn[u], Q[cnt].l = dfn[v], Q[cnt].val = k, Q[cnt].id = i;
    }
    std::sort(H + 1, H + 1 + hcnt), hcnt = std::unique(H + 1, H + 1 + hcnt) - H - 1;
    std::sort(Q + 1, Q + 1 + cnt, cmp);
    solve(1, hcnt, 1, cnt);
    for (int i = 1; i <= q; ++i) printf("%d\n",H[ans[i]]);
    return 0;
}
本文标题:[Luogu] [HNOI2015]接水果
本文作者:Clouder
本文链接: https://www.codein.icu/lp3242/
转载请标明。

评论

  1. 3月前
    2020-10-27 12:52:48

    您切题量都快有我两倍了%%%

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇