洛谷3242 [HNOI2015]接水果

Luogu

分析

神仙题。

前置知识:路径的包含关系

设 $st[u]$ 表示 $u$ 的$\mathrm{dfs}$序, $ed[u]$ 表示 $u$ 的子树中最大的 $st[u]$。

假设 $(u,v)$ 是一个盘子的两端, $(a,b)$ 是一个水果的两端,并且 $(a,b)$ 包含 $(u,v)$ ,分两种情况讨论:

  • $u$ 和 $v$ 都不是 $\mathrm{LCA}$

此时 $a$ 在 $u$ 的子树中, $b$ 在 $v$ 的子树中,那么显然有 $st[u]\leq st[a] \leq ed[u],st[v]\leq st[b]\leq ed[v]$。

  • $u$ 或者 $v$ 是 $\mathrm{LCA}$

假设 $v$ 是 $\mathrm{LCA}$。

此时 $a$ 在 $u$ 的子树内, $b$ 在这条链外。

然后显然有 $st[v]\leq st[a]\leq ed[v]$。

设 $(u,v)$ 链上 $v$ 的儿子为 $w$。

于是有 $st[b]<st[w]\ \mathrm{or}\ ed[w]<st[b]$。

题解

发现,如果把盘子的 $(st[u],st[v])$ 和 $(ed[u],ed[v])$ 看作一个矩形的对角的两个点,那么一个水果 $(a,b)$ 能被 $(u,v)$ 接到,当且仅当 $(st[a],st[b])$ 在这个矩形内。

然后就可以用扫描线来处理水果能被多少个盘子接了。

题目要求第 $k$ 小的,于是套个整体二分就好了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10;

//结构体和重载
struct Matrix { int x1,y1,x2,y2,k; } t[N];
struct Fruit { int x,y,k,id; } q[N],lq[N],rq[N];
struct Line { int y1,y2,x,v; } p[N];
bool operator <(Matrix a,Matrix b) { return a.k<b.k; }
bool operator <(Fruit a,Fruit b) { return a.x<b.x; }
bool operator <(Line a,Line b) { return a.x<b.x; }

//邻接表
struct Edge { int v,nxt; } e[N];
int head[N],cnt=0;

inline void addEdge(int u,int v) {
    e[++cnt]=(Edge){v,head[u]},head[u]=cnt;
}

//变量
int n,P,Q;
int f[18][N],dep[N];
int st[N],ed[N],dfs_clock=0,tot=0;
int ans[N];

//树状数组
int c[N];
#define lowbit(x) (x&-x)
inline void add(int x,int y) {
    for (;x<=n;x+=lowbit(x)) c[x]+=y;
}
inline int sum(int x) {
    int ans=0;
    for (;x;x-=lowbit(x)) ans+=c[x];
    return ans;
}

//函数
inline void dfs(int u,int fa) {
    f[0][u]=fa,dep[u]=dep[fa]+1,st[u]=++dfs_clock;
    for (re int i=1;i<=15;++i) f[i][u]=f[i-1][f[i-1][u]];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u);
    }
    ed[u]=dfs_clock;
}

inline int LCA(int u,int v,int op) {
    if (dep[u]<dep[v]) swap(u,v);
    for (re int i=15;i>=0;--i)
        if (dep[f[i][u]]>dep[v]) u=f[i][u];
    if (f[0][u]==v) return op?u:v;
    u=f[0][u];
    for (re int i=15;i>=0;--i)
        if (f[i][u]!=f[i][v]) u=f[i][u],v=f[i][v];
    return op?u:f[0][u];
}

inline void solve(int L,int R,int lval,int rval) {
    if (L>R) return;
    if (lval==rval) {
        for (re int i=L;i<=R;++i) ans[q[i].id]=lval;
        return;
    }
    int mid=(lval+rval)>>1,lt=0,rt=0,cnt=0;
    for (re int i=lval;i<=mid;++i) {
        p[++cnt]=(Line){t[i].y1,t[i].y2,t[i].x1,1};
        p[++cnt]=(Line){t[i].y1,t[i].y2,t[i].x2+1,-1};
    }
    sort(p+1,p+cnt+1);
    int pos=1;
    for (re int i=L;i<=R;++i) {
        while (pos<=cnt&&p[pos].x<=q[i].x)
            add(p[pos].y1,p[pos].v),add(p[pos].y2+1,-p[pos].v),++pos;
        int s=sum(q[i].y);
        if (q[i].k<=s) lq[++lt]=q[i];
        else q[i].k-=s,rq[++rt]=q[i];
    }
    for (re int i=1;i<pos;++i)
        add(p[i].y1,-p[i].v),add(p[i].y2+1,p[i].v);
    for (re int i=1;i<=lt;++i) q[L+i-1]=lq[i];
    for (re int i=1;i<=rt;++i) q[L+lt+i-1]=rq[i];
    solve(L,L+lt-1,lval,mid),solve(L+lt,R,mid+1,rval);
}

int main() {
    n=read(),P=read(),Q=read();
    for (re int i=1;i<n;++i) {
        int u=read(),v=read();
        addEdge(u,v),addEdge(v,u);
    }
    dfs(1,0);
    for (re int i=1;i<=P;++i) {
        int u=read(),v=read(),k=read();
        if (st[u]>st[v]) swap(u,v);
        int lca=LCA(u,v,0);
        if (u!=lca) t[++tot]=(Matrix){st[u],st[v],ed[u],ed[v],k};
        else {
            int d=LCA(u,v,1);
            if (st[d]!=1) t[++tot]=(Matrix){1,st[v],st[d]-1,ed[v],k};
            if (ed[d]!=n) t[++tot]=(Matrix){st[v],ed[d]+1,ed[v],n,k};
        }
    }
    for (re int i=1;i<=Q;++i) {
        int u=read(),v=read(),k=read();
        if (st[u]>st[v]) swap(u,v);
        q[i]=(Fruit){st[u],st[v],k,i};
    }
    sort(t+1,t+tot+1); sort(q+1,q+Q+1);
    solve(1,Q,1,tot);
    for (re int i=1;i<=Q;++i) printf("%d\n",t[ans[i]].k);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 11 PM

发表评论