整体二分题解

扫描线整体二分（偏序整体二分）

P3242 [HNOI2015] 接水果

这是一道极好的神仙题，除了博弈论几乎没有任何其它题的思维有这题巧妙，其天才般的思想和知识点间美妙的融合让所有 OIer 叹为观止。确切地说，这是我此生见过的最巧妙的题，整体二分的实现也不由得让人对出题者产生由衷的钦佩。

注意到这居然是省选题。注意到我不知道风见幽香是谁。注意到这题居然是用盘子接水果而不是水果接盘子，盘子要被水果包含才能装住水果。

树上第 k 小，考虑整体二分，因为我们这篇的标题中整体二分排在最前面。假设我们的盘子是以下蓝色链条，x 和 y 是盘子的两个端点，z 是 x 在盘子上的儿子，能装住盘子的水果的两个端点为 u,v, 其中 $dep_u<dep_v$（如果不是则将两个端点交换）, u 和 v 的最近公共祖先是 u：

此时图中红色的部分即是 u 可能的范围，蓝色的部分即是 v 可能的范围。

如果 u 不是 v 的祖先，则：

可贡献的图就如上所示了。因此，询问 $(x,y)$ 与 $\operatorname{lca}_{u,v}=u$ 时 $st_u\in [1,st_z)|(ed_z,N],st_v\in [st_y,ed_y]$ 和当不满足 $\operatorname{lca}_{u,v}=u$ 时 $st_u\in [st_x,ed_x],st_v\in [st_y,ed_y]$ 的果子 $(u,v)$ 有关。我们注意到这个约束条件很像是矩形，把每个盘子看作一个矩形，它能装住的所有点都是能接住的果子。问题转化为求一个点所在的所有矩形中第 $k$ 小的权值，判断时将 $[0,mid]$ 的所有矩形加一然后单点查询。可以在每次整体二分中排序，然后用扫描线求出被标记的数有多少个并进行二分。由于扫描线自带一次撤销操作，因此不用在整体二分后再清空树状数组。

这个扫描线没有面积并和周长并里的那么麻烦，只需要在扫到入边时加权，扫到出边时减回去（是个人都会做）。

Code：

#include<bits/stdc++.h>
using namespace std;
#define mid (l+r>>1)
#define re register
#define il inline
int n,m,q,t[40005],ans[40005],b[40005],tot,head[40005],to[80005],nxt[80005],cnt,ttl,id,top[40005],dep[40005],sz[40005],son[40005],fa[40005],st[40005],ed[40005],k,x,y,s,z,qcnt;
struct xyl{int op,x,l,r,k,v,id;bool operator<(const xyl&s)const{return x^s.x?x<s.x:op<s.op;}}a[200005],q1[200005],q2[200005];
il void add(int x,int d){for(;x<=n;x+=x&-x)t[x]+=d;}
il int qry(int x){re int res=0;for(;x;x^=x&-x)res+=t[x];return res;}
il void link(int x,int y){to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt,to[++cnt]=x,nxt[cnt]=head[y],head[y]=cnt;}
void dfs1(int u,int lst){
    fa[u]=lst,sz[u]=1,dep[u]=dep[lst]+1;
    for(re int i=head[u];i;i=nxt[i])
        if(lst^to[i]){
            dfs1(to[i],u);
            sz[u]+=sz[to[i]];
            if(sz[to[i]]>sz[son[u]])son[u]=to[i];
        }
}
void dfs2(int u,int topx){
    top[u]=topx,st[u]=++ttl;
    if(son[u])dfs2(son[u],topx);
    for(re int i=head[u];i;i=nxt[i])
        if(to[i]^fa[u]&&to[i]^son[u])dfs2(to[i],to[i]);
    ed[u]=ttl;
}
il int lca(int x,int y){
    while(top[x]^top[y])dep[top[x]]>dep[top[y]]?x=fa[top[x]]:y=fa[top[y]];
    return dep[x]<dep[y]?x:y;
}
il int theson(int x,int y){
    while(top[x]^top[y]){if(fa[top[x]]^y)x=fa[top[x]];else return top[x];}
    return son[y];
}
void solve(int ql,int qr,int l,int r){
    if(ql>qr)return;
    if(l==r){
        for(re int i=ql;i<=qr;++i)
            if(a[i].op==2)ans[a[i].id]=l;
        return;
    }
    re int c1=0,c2=0;
    for(re int i=ql;i<=qr;++i){
        if(a[i].op^2){
            if(a[i].k<=mid)add(a[i].l,a[i].v),add(a[i].r+1,-a[i].v),q1[++c1]=a[i];
            else q2[++c2]=a[i];
        }
        else{
            k=qry(a[i].l);
            if(a[i].k<=k)q1[++c1]=a[i];
            else a[i].k-=k,q2[++c2]=a[i];
        }
    }
    for(re int i=1;i<=c1;++i)a[ql+i-1]=q1[i];
    for(re int i=1;i<=c2;++i)a[ql+c1+i-1]=q2[i];
    solve(ql,ql+c1-1,l,mid),solve(ql+c1,qr,mid+1,r);
}
il int read(){
    re int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
il void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked((x%10)|48);
}
signed main(){
    n=read(),m=read(),q=read();
    for(re int i=1;i<n;++i)link(read(),read());
    dfs1(1,0),dfs2(1,1);
    for(re int i=1;i<=m;++i){
        x=read(),y=read(),b[i]=s=read();
        if(st[x]>st[y])x^=y^=x^=y;
        if(lca(x,y)^x)a[++qcnt]={1,st[x],st[y],ed[y],s,1,0},a[++qcnt]={1,ed[x]****t[y],ed[y],s,-1,0};
        else{
            z=theson(y,x);
            if(st[z]>1)a[++qcnt]={1,1,st[y],ed[y],s,1,0},a[++qcnt]={1,st[z],st[y],ed[y],s,-1,0};
            if(ed[z]<n)a[++qcnt]={1,st[y],ed[z]+1,n,s,1,0},a[++qcnt]={1,ed[y]+1,ed[z]+1,n,s,-1,0};
        }
    }
    sort(b+1,b+m+1),tot=unique(b+1,b+m+1)-b-1;
    for(re int i=1;i<=qcnt;++i)a[i].k=lower_bound(b+1,b+tot+1,a[i].k)-b;
    for(re int i=1;i<=q;++i){
        x=read(),y=read(),s=read();
        if(st[x]>st[y])x^=y^=x^=y;
        a[++qcnt]={2,st[x],st[y],0,s,0,i};
    }
    sort(a+1,a+qcnt+1),solve(1,qcnt,1,tot);
    for(re int i=1;i<=q;++i)write(b[ans[i]]),putchar_unlocked('\n');
    return 0;
}

成功拿到此题最优解：