虚式优化建图题。
首先有一个很显然的暴力，对于两条相交的线段连一条边，然后跑割点。
这个暴力的问题在于边与点的时间复杂度相差过大，无论是空间还是时间都无法承受，所以可以想到去优化建图。
首先我们假设点与边的复杂度相同，那么我们空间是承受的下的，现在想要时间承受下，由于是二维平面图，很容易想到去用扫描线。用垂直的直线去扫，扫到左端点连边，扫到右端点后不再连边，可以用队列维护。
基于这个思路，我们在这道题也用扫描线，但是队列里的元素过多，是无法承受的，乍一看队列里的元素是没有规律的，但是对于一条水平线，它进出时间是连续的，所以根据它的进出时间来判断，左端点入队，右端点出队，用线段树维护，由于每个版本都是需要用到的，显然使用主席树即可。
那么我们处理出了每个垂直线段与水平线段的相交情况，那么再横着扫一次，就处理出了每个水平线段与垂直线段的相交情况。
现在我们把所有的相交情况处理到了一棵主席树上，我们要拿它去跑割点，问题在于怎么去跑。
我们知道我们在跑割点时，维护了 \(dfn,low\) 两个值，而 \(dfn\) 是不变的，所以不需要管它，在转移 \(low\) 时，我们要判断这个点是否被遍历过，记为 \(vis\) 数组。
所以现在我们要动态维护 \(low,vis\)，这东西好像直接在遍历的时候改一下值就行了……
处理好动态维护，下一个的就是遍历点了，如何得到这个点连向的下一个未被遍历的点呢。
我们首先先预处理出每个区间未使用过的点，初始时就对于每一个顶层节点 \(+1\) 然后往上 \(pushup\)。当遍历到那个节点时，将其所在的节点 \(-1\)，往上 \(pushup\) 即可。
最后一步即是求连接的点中最小的 \(dfn\) 值，虽然对于由它转移出去的点是由 \(low\) 值转移的，但众所周知 \(low\le dfn\) 所以不会影响，那么这个好弄，在第一遍历到这个节点时在对应节点修改，最后维护区间最小值即可。
注意处理根节点的情况，根节点是遍历节点数大于二才为割点。
时间复杂度：\(O(n\log(n))\)
点击查看代码
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
const int N=2e5+5;
int n,L[N],R[N],m,cnt,p[N],ans[N],dfn[N],low[N],rt[N],cnp;
vector<int>a[N],b[N];
namespace tree
{
struct node
{
int ls,rs,minn,sum;
}f[40*N];
inline void pushup(int x)
{
//cout<<x<<" "<<f[x].ls<<" "<<f[x].rs<<" "<<f[f[x].ls].minn<<" "<<f[f[x].rs].minn<<endl;
f[x].sum=f[f[x].ls].sum+f[f[x].rs].sum;
f[x].minn=min(f[f[x].ls].minn,f[f[x].rs].minn);
}
void update(int &x,int y,int l,int r,int nl,int k)
{
if(!x)x=++cnt;
f[x]=f[y];
if(l==r)
{
f[x].sum+=k;
if(k==1)p[nl]=x;
return;
}
int mid=(l+r)>>1;
if(mid>=nl)update(f[x].ls=0,f[y].ls,l,mid,nl,k);
else update(f[x].rs=0,f[y].rs,mid+1,r,nl,k);
pushup(x);
}
int search(int x,int l,int r,int nl,int nr)
{
//cout<<x<<" "<<l<<" "<<r<<" "<<nl<<" "<<nr<<" "<<f[x].minn<<endl;//1666
if(!x||(l>=nl&&r<=nr))return f[x].minn;
int mid=(l+r)>>1,ans=1e9;
if(mid>=nl)ans=min(ans,search(f[x].ls,l,mid,nl,nr));
if(mid<nr)ans=min(ans,search(f[x].rs,mid+1,r,nl,nr));
return ans;
}
int getnode(int x,int l,int r,int nl,int nr)
{
if(!f[x].sum)return 0;
if(l==r)
{
//cout<<x<<endl;
f[x].sum=0;
f[x].minn=++cnp;
return l;
}
int mid=(l+r)>>1;
int num=0;
if(mid>=nl)num=getnode(f[x].ls,l,mid,nl,nr);
if(num)
{
pushup(x);
return num;
}
if(mid<nr)
{
int num=getnode(f[x].rs,mid+1,r,nl,nr);
pushup(x);
return num;
}
pushup(x);
return 0;
}
}
using namespace tree;
void Tarjan(int x,bool ss)
{
int son=0;
dfn[x]=low[x]=cnp;
int i=getnode(rt[x],1,m,L[x],R[x]);
//cout<<endl;
for(;i;i=getnode(rt[x],1,m,L[x],R[x]))
{
//cout<<endl;
son++;
Tarjan(i,1);
low[x]=min(low[x],low[i]);
//cout<<x<<" "<<i<<" "<<L[i]<<" "<<R[i]<<" "<<dfn[x]<<" "<<low[i]<<endl;
if(dfn[x]==low[i])ans[x]=1;
}
low[x]=min(low[x],search(rt[x],1,m,L[x],R[x]));
if(!ss)ans[x]=son>1;
}
int main()
{
// freopen("segment4.in","r",stdin);
// freopen("data.out","w",stdout);
scanf("%d",&n);
m=2*n;
for(int i=1;i<=n;i++)scanf("%d%d",&L[i],&R[i]),L[i]+=n,R[i]+=n;
for(int i=1;i<=n;i++)scanf("%d%d",&L[i+n],&R[i+n]);
for(int i=1;i<=m;i++)a[L[i]].push_back(i),b[R[i]+1].push_back(i);
f[0].minn=1e9;
for(int i=1;i<=m;i++)
{
rt[i]=++cnt;
f[rt[i]]=f[rt[i-1]];
int len=a[i].size();
for(int j=0;j<len;j++)update(rt[i],rt[i],1,m,a[i][j],1);
len=b[i].size();
for(int j=0;j<len;j++)update(rt[i],rt[i],1,m,b[i][j],-1);
}
// cout<<cnt<<endl;
//cout<<f[82].ls<<" "<<f[82].rs<<endl;
for(int i=1;i<=m;i++)if(!dfn[i])f[p[i]].sum=0,f[p[i]].minn=++cnp,Tarjan(i,0);
//for(int i=1;i<=m;i++)cout<<i<<" "<<dfn[i]<<" "<<low[i]<<endl;
for(int i=1;i<=n;i++)printf("%d",ans[i]);
printf("\n");
for(int i=1;i<=n;i++)printf("%d",ans[i+n]);
printf("\n");
return 0;
}