Description

先给出一些盘子, 用路径x-y表示, 有权值

再有Q个询问, 表示水果, 用路径x-y表示

如果盘子是水果的子路径, 可以接住

对于每个水果, 输出可以接住它的盘子的第k小权

Solution

对于x-lca-y的盘子，水果一定一个在x子树，一个在y子树

对于x-lca的盘子，水果一定一个在x子树，一个在lca的非x子树，即dfn序中的两段区间

将一对区间(盘子)、一对点(水果)按dfn序顺序转化成一个矩形(盘子)和一个坐标(水果)

很明显就是整体二分了

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cctype>

using namespace std;

typedef long long LL;

const int M=40007;

inline int rd(){

    int x=0;bool f=1;char c=getchar();

    for(;!isdigit(c);c=getchar())if(c=='-')f=0;

    for(;isdigit(c);c=getchar())x=x*10+c-48;

    return f?x:-x;

}

int n,m,Q;

int g[M];

struct edge{int y,next;}e[M<<1];

int top[M],pre[M],dep[M],sz[M],son[M];

int st[M],ed[M],pid[M];

struct pp{int d,id;}bb[M];

bool cd(pp x,pp y){return x.d<y.d;}

int val[M],tt;

struct plate{int x,y,z;}pan[M];

int nd[M],tmp[M],ans[M];

struct opr{

    int x,y,z,kd;

    opr(int xx=0,int yy=0,int zz=0,int kk=0){x=xx;y=yy;z=zz;kd=kk;}

}q[M*9],q1[M*9],q2[M*9],a[M*9];

int tot,ta;

bool dx(opr x,opr y){

    if(x.x==y.x&&x.y==y.y) return x.kd<y.kd;

    if(x.x==y.x) return x.y>y.y;

    return x.x>y.x;

}

int c[M],col[M],T;

void addedge(int x,int y){

    e[++tot].y=y;e[tot].next=g[x];g[x]=tot;

}

inline int lb(int x){return x&-x;}

void add(int x,int d){

    for(;x>0;x-=lb(x)){

        if(col[x]!=T){

            col[x]=T;

            c[x]=0;

        }

        c[x]+=d;

    }

}

int get(int x){

    int res=0;

    for(;x<=n;x+=lb(x))

        if(col[x]==T) res+=c[x];

    return res;

}

void dfs1(int x){

    sz[x]=1;

    int p,y;

    for(p=g[x];p;p=e[p].next)

    if((y=e[p].y)!=pre[x]){

        pre[y]=x;

        dep[y]=dep[x]+1;

        dfs1(y);

        sz[x]+=sz[y];

        if(sz[y]>sz[son[x]]) son[x]=y;

    }

}

void dfs2(int x){

    int p,y;

    pid[st[x]=++T]=x;

    if(son[x]){

        top[son[x]]=top[x];

        dfs2(son[x]);

    }

    for(p=g[x];p;p=e[p].next)

    if((y=e[p].y)!=pre[x]&&y!=son[x]){

        top[y]=y;

        dfs2(y);

    }

    ed[x]=T;

}

int getlca(int x,int y){

    while(top[x]!=top[y]){

        if(dep[top[x]]<dep[top[y]]) swap(x,y);

        x=pre[top[x]];

    }

    if(dep[x]>dep[y]) swap(x,y);

    return x;

}

int jump(int x,int y){

    while(dep[top[x]]>dep[y]){

        x=top[x];

        if(pre[x]==y) return x;

        x=pre[x];

    }

    return pid[st[y]+1];

}

void addrectangle(int xx,int yy,int x,int y,int z){

    q[++tot]=opr(xx-1,yy-1,z,1);

    q[++tot]=opr(x,y,z,1);

    q[++tot]=opr(xx-1,y,z,-1);

    q[++tot]=opr(x,yy-1,z,-1);

}

void gao(){

    int i;

    sort(a+1,a+ta+1,dx);

    for(T++,i=1;i<=ta;i++){

        if(a[i].kd!=2) add(a[i].y,a[i].kd);

        else tmp[a[i].z]+=get(a[i].y);

    }

}

void solve(int l,int r,int L,int R){

    if(l>r) return;

    int i,j,t1=0,t2=0,mid=L+R>>1;

    if(L==R){

        for(i=l;i<=r;i++)

            if(q[i].kd==2) ans[q[i].z]=val[L];

        return;

    }

    ta=0;

    for(i=l;i<=r;i++){

        if(q[i].kd==2) a[++ta]=q[i],tmp[q[i].z]=0;

        else if(q[i].z<=mid) a[++ta]=q[i];

    }

    gao();

    for(i=l;i<=r;i++){

        if(q[i].kd!=2){

            if(q[i].z<=mid) q1[++t1]=q[i];

            else q2[++t2]=q[i];

        }

        else{

            if(nd[q[i].z]<=tmp[q[i].z]) q1[++t1]=q[i];

            else{

                nd[q[i].z]-=tmp[q[i].z];

                tmp[q[i].z]=0;

                q2[++t2]=q[i];

            }

        }

    }

    for(i=1;i<=t1;i++) q[l+i-1]=q1[i];

    for(i=1;i<=t2;i++) q[l+t1+i-1]=q2[i];

    solve(l,l+t1-1,L,mid);

    solve(l+t1,r,mid+1,R);

}

int main(){

    int i,x,y,xx,yy,z,lc;

    n=rd(),m=rd(),Q=rd();

    for(i=1;i<n;i++){

        x=rd();

        y=rd();

        addedge(x,y);

        addedge(y,x);

    }

    dep[1]=1;dfs1(1);top[1]=1;dfs2(1);

    for(i=1;i<=m;i++){

        pan[i].x=rd(),pan[i].y=rd();

        bb[i].d=rd();bb[i].id=i;

    }

    sort(bb+1,bb+m+1,cd);bb[0].d=bb[1].d-1;

    for(i=1;i<=m;i++){

        if(bb[i].d!=bb[i-1].d) val[++tt]=bb[i].d;

        pan[bb[i].id].z=tt;

    }

    for(i=1;i<=m;i++){

        x=pan[i].x;

        y=pan[i].y;

        if(st[x]>st[y]) swap(x,y);

        lc=getlca(x,y);

        if(lc!=x&&lc!=y){

            addrectangle(st[x],st[y],ed[x],ed[y],pan[i].z);

        }

        else{

            if(lc!=x) swap(x,y);

            lc=jump(y,x);

            if(st[lc]>1) addrectangle(1,st[y],st[lc]-1,ed[y],pan[i].z);

            if(ed[lc]<n) addrectangle(st[y],ed[lc]+1,ed[y],n,pan[i].z);

        }

    }

    for(i=1;i<=Q;i++){

        x=st[rd()],y=st[rd()];

        if(x>y) swap(x,y);

        nd[i]=rd();

        q[++tot]=opr(x,y,i,2);

    }

    solve(1,tot,1,tt);

    for(i=1;i<=Q;i++) printf("%d\n",ans[i]);

    return 0;

}

巴特西

bzoj 4009 接水果整体二分

Description

Solution

最新文章

热门文章

巴特西

bzoj 4009 接水果 整体二分

Description

Solution

最新文章

热门文章

bzoj 4009 接水果整体二分