[HNOI2015]接水果

Description:

给你一棵树和一个路径集合,每次询问某条给定路径包含的路径集合中第k大的路径的权值

Hint:

\(n,m\le 50000\)

Solution:

毒瘤题

先考虑这个包含的条件怎么判断? 先把原树的dfn求出来

1.如果两点没有祖先关系,则显然所求路径的端点分别位于两点子树中

即: \(dfn[a] \le x \le dfn[a]+sz[a]-1\) \(dfn[b] \le y \le dfn[b]+sz[b]-1\)

2.如果有祖先关系,则路径一端不变,另一端除这棵子树内其他位置都合法

即 \(dfn[a] \le x \le dfn[a]+sz[a]-1\) \(1 \le y \le dfn[b]+1\ \ or\ \ dfn[b]+sz[b] \le y \le n\)

把路径集合看成矩形

询问就是在求覆盖一个点的矩形中第k大的那个

考虑整体二分,把这些矩形按权值排序

每次递归时扫描线算出一个点被覆盖的次数,某时刻满足刚刚被覆盖k次,则找到答案

复杂度\(O(nlog^2n)\)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=1e5+5;
int n,m,q,z,pl,df,ct,cnt;
int c[mxn],hd[mxn],dfn[mxn],lst[mxn],dep[mxn],res[mxn],ans[mxn];
int f[mxn][18];

inline int read() {
    char c=getchar(); int x=0,f=1;
    while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
    while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
    return x*f;
}
inline void chkmax(int &x,int y) {if(xy) x=y;}

struct ed {
    int to,nxt;
}e[mxn<<1];

inline void add(int u,int v) {
    e[++ct]=(ed) {v,hd[u]}; hd[u]=ct;
}

struct P {
    int x1,x2,y1,y2,val,id;
    friend bool operator < (P a,P b) {
        return a.val=0;--i) 
        if(dep[f[x][i]]>=dep[y])
            x=f[x][i];
    if(x==y) return x;
    for(int i=16;i>=0;--i) 
        if(f[x][i]!=f[y][i])
            x=f[x][i],y=f[y][i];
    return f[x][0];		
}

void dfs(int u,int fa) {
    dfn[u]=++df; dep[u]=dep[fa]+1; f[u][0]=fa;
    for(int i=hd[u];i;i=e[i].nxt) {
        int v=e[i].to;
        if(v==fa) continue ;
        dfs(v,u); 
    }
    lst[u]=df;
}

void solve(int l,int r,int ql,int qr) {
    if(ql>qr) return ;
    if(l==r) {
        for(int i=ql;i<=qr;++i) ans[fr[i].id]=plt[l].val;
        return ;
    }
    int mid=(l+r)>>1,tot=0,L=0,R=0;
    for(int i=l;i<=mid;++i) {
        t[++tot]=(T){plt[i].x1,plt[i].y1,plt[i].y2,1,0};
        t[++tot]=(T){plt[i].x2,plt[i].y1,plt[i].y2,-1,n+1};
    }
    for(int i=ql;i<=qr;++i) t[++tot]=(T){fr[i].x,fr[i].y,0,0,i};
    sort(t+1,t+tot+1);
    for(int i=1;i<=tot;++i) 
        if(ql<=t[i].id&&t[i].id<=qr) res[t[i].id]=query(t[i].l);
        else mod(t[i].l,t[i].r,t[i].val);
    for(int i=ql;i<=qr;++i) 
        if(res[i]>=fr[i].k) tl[++L]=fr[i];
        else tr[++R]=(F){fr[i].x,fr[i].y,fr[i].k-=res[i],fr[i].id};
    for(int i=ql;i<=ql+L-1;++i) fr[i]=tl[i-ql+1];
    for(int i=ql+L;i<=qr;++i) fr[i]=tr[i-ql-L+1];
    solve(l,mid,ql,ql+L-1); solve(mid+1,r,ql+L,qr);
}

int main()
{
    n=read(); m=read(); q=read(); int u,v,w,x,y;
    for(int i=1;idfn[v]) swap(u,v);
        if(x!=u) plt[++cnt]=(P){dfn[u],lst[u],dfn[v],lst[v],w};
        else {
            x=dep[v]-dep[u]-1; y=v;
            for(int i=16;i>=0;--i) 
                if(x>=(1<dfn[v]) swap(u,v);
        fr[i]=(F){dfn[u],dfn[v],w,i};
    }
    solve(1,cnt,1,q);
    for(int i=1;i<=q;++i) printf("%d\n",ans[i]);
    return 0;
}
扫描线整体二分

相关

bzoj4009 [HNOI2015]接水果 整体二分+扫描线+树状数组+dfs序

Leetcode 252. 会议室 253. 会议室II 贪心算法-扫描线技巧

【Codeforces】【网络流】【线段树】【扫描线】Oleg and chess (CodeForces - 793G)

dls的数据结构-扫描线与权值线段树

leetcode(c++)(扫描线)

UOJ637 数据结构 - 扫描线、线段树

标签