P7712 [Ynoi2077] hlcpq（割点 + 优化建图）

· · 题解

常见优化建图技巧

先考虑如何优化题目中给出的建图方式。

首先显然只可能水平线段和竖直线段相交。

考虑对于一个水平线段，如何求出和它相交的竖直线段。

对于每个竖直线段的端点 y 坐标，和水平线段的 y 坐标，从小到大排序。在上端点处加入竖直线段，下端点处删除。用线段树维护所有加入的竖直线段的 x 坐标，则与某条水平线段相交的竖直线段，位于线段树上的一段区间。

需要维护线段树在不同 y 坐标的版本，可持久化即可。

但是我们并不能直接将主席树的点作为虚点，优化建图，因为有可能一些虚点变为割点，导致原图割点减少。

考虑 P5471 [NOI2019] 弹跳 的做法，不直接建出所有边。

观察以下求割点的代码：

void tar(int x){
    int c=0,i=he[x],j;
    for(dfn[x]=low[x]=++id;i;i=ne[i])if(!dfn[j=to[i]]){
        tar(j),++c,low[x]=min(low[x],low[j]);
        if(low[j]==dfn[x])f[x]=1;
    }else low[x]=min(low[x],dfn[j]);
    if(x==r)f[x]=c>1;
}

发现 if 里面的部分只会运行 O(n) 次，可以直接暴力。

但是我们需要知道哪些点会进入 if，即哪些点没有被访问过。

考虑对主席树上每个点维护一个值 w，表示这个点子树内没有被访问过的点个数，若这个值大于 0 则继续向下递归，然后 pushup 时更新这个值。访问一个点时找到对应的主席树上的叶子，将这个值改成 0。

然后是对已经访问过的点 low[x]=min(low[x],dfn[j])，注意到 low_x\leq dfn_x，而对于未访问过的点有 low[x]=min(low[x],low[j])，所以我们可以改为对所有点进行 low[x]=min(low[x],dfn[j])。

需要在主席树上多维护一个值 m 表示 \min dfn_j，在访问到一个点时修改即可，容易发现这个值和 w 是同时被修改的，所以可以同时 pushup。

每次向下递归一定是找到一个未访问过的点，或者对经过的所有点更新 w=0，所以复杂度均摊是 O(n\log n) 的。

const int N=2e5+3;
int al[N],ar[N],m,rt[N],nd,id,u,v,p[N],low[N],dfn[N];
bool ans[N];
basic_string<int>ad[N],dl[N];
struct T{
    int w,m,l,r;
}t[N*40];
void upd(int&k,int l,int r){//插入和删除
    if(t[++nd]=t[k],k=nd,t[k].w+=v,l==r){
        if(v==1)p[l]=k;
        return;
    }
    int m=l+r>>1;
    u>m?upd(t[k].r,m+1,r):upd(t[k].l,l,m);
}
void up(int k){t[k].w=t[t[k].l].w+t[t[k].r].w,t[k].m=min(t[t[k].l].m,t[t[k].r].m);}
int get(int k,int l,int r){//找点
    if(!t[k].w)return 0;
    if(l==r)return t[k].w=0,t[k].m=++id,l;
    int m=l+r>>1,i;
    if(u<=m)if(i=get(t[k].l,l,m))return up(k),i;
    if(m<v)if(i=get(t[k].r,m+1,r))return up(k),i;
    return up(k),0;
}
int qry(int k,int l,int r){//求最小值
    if(!k||u<=l&&r<=v)return t[k].m;
    int m=l+r>>1;
    if(u<=m)return m<v?min(qry(t[k].l,l,m),qry(t[k].r,m+1,r)):qry(t[k].l,l,m);
    return qry(t[k].r,m+1,r);
}
void tar(int x,bool b){//求割点
    int c=0,i;
    for(dfn[x]=low[x]=id;u=al[x],v=ar[x],i=get(rt[x],1,m);){
        tar(i,0),++c,low[x]=min(low[x],low[i]);
        if(low[i]==dfn[x])ans[x]=1;
    }
    if(u=al[x],v=ar[x],low[x]=min(low[x],qry(rt[x],1,m)),b)ans[x]=c>1;
}
int main(){
    int n,i;
    for(scanf("%d",&n),i=1;i<=n;++i)scanf("%d%d",al+i,ar+i),ad[al[i]+=n]+=i,dl[(ar[i]+=n)+1]+=i;
    for(t[0].m=N,m=n*2;i<=m;++i)scanf("%d%d",al+i,ar+i),ad[al[i]]+=i,dl[ar[i]+1]+=i;
    for(i=1;rt[i]=rt[i-1],i<=m;++i){
        for(auto o:ad[i])u=o,v=1,upd(rt[i],1,m);
        for(auto o:dl[i])u=o,v=-1,upd(rt[i],1,m);
    }
    for(i=1;i<=m;++i)if(!dfn[i])t[p[i]]={0,++id,0,0},tar(i,1);
    for(i=1;i<=n;++i)cout<<ans[i];
    for(puts("");i<=m;++i)cout<<ans[i];
    return 0;
}