Problem Statement
For an integer sequence $X=(X_1,X_2,\dots,X_n)$, let $X[L,R]$ denote the integer sequence $(X_L,X_{L+1},\dots,X_{R})$.
You are given integers $N$ and $M$, and $M$ quadruples of integers $(A_i,B_i,C_i,D_i)$.
Determine if there is an integer sequence $X$ of length $N$ that satisfies the following condition for every $i=1,2,\dots,M$:
- $X[A_i,B_i]$ is lexicographically smaller than $X[C_i,D_i]$.
What is lexicographical order on sequences?
A sequence $S = (S_1,S_2,\ldots,S_{|S|})$ is lexicographically smaller than $T = (T_1,T_2,\ldots,T_{|T|})$ when 1. or 2. below holds. Here, $|S|$ and $|T|$ denotes the lengths of $S$ and $T$, respectively.
- $|S| \lt |T|$ and $(S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})$.
- There is an integer $1 \leq i \leq \min\lbrace |S|, |T| \rbrace$ that satisfy both of the following:
- $(S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})$.
- $S_i$ is smaller than $T_i$ (as a number).
Constraints
- $2 \leq N \leq 2000$
- $1 \leq M \leq 2000$
- $1 \leq A_i \leq B_i \leq N$
- $1 \leq C_i \leq D_i \leq N$
- All input values are integers.
首先一定满足 \(X_{A_i}\le X_{C_i}\)，从 \(A_i\) 向 \(C_i\) 连边。
跑一次 tarjan 后，此时如果出现了大于 1 的强连通分量，那么这个分量里所有的数都是一样的，用一个并查集并起来。
如果这个强连通分量里的边有 \(i\)，那么说明 \(X_{A_{i+1}}\le X_{C_{i+1}}\)
以此类推，知道某一次没有大于 1 的强连通分量，就结束了。
发现每次至少合并两个点，最多跑 \(N\) 次 tarjan。同时每次图中至多有 \(M\) 条边，所以复杂度是 \(O(NM)\) 的。
#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int n,m,k,tp,st[N],hd[N],fl,e_num,tme,p[N],id[N],dfn[N],low[N],idx,a[N],b[N],c[N],d[N],fa[N];
struct edge{
int v,nxt;
}e[N];
void add_edge(int u,int v)
{
e[++e_num]=(edge){v,hd[u]};
hd[u]=e_num;
}
int find(int x)
{
if(fa[x]==x)
return x;
return fa[x]=find(fa[x]);
}
void tarjan(int x)
{
dfn[x]=low[x]=++tme;
st[++tp]=x;
for(int i=hd[x];i;i=e[i].nxt)
{
if(!dfn[e[i].v])
tarjan(e[i].v),low[x]=min(low[x],low[e[i].v]);
else if(!id[e[i].v])
low[x]=min(low[x],dfn[e[i].v]);
}
if(low[x]==dfn[x])
{
++idx;
if(st[tp]^x)
{
fl=1;
while(st[tp]^x)
id[st[tp]]=idx,fa[find(st[tp--])]=find(x);
}
id[st[tp--]]=idx;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",a+i,b+i,c+i,d+i);
add_edge(a[i],c[i]);
}
while(1)
{
fl=tme=idx=0;
memset(dfn,0,sizeof(dfn));
memset(id,0,sizeof(id));
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
if(!fl)
break;
memset(hd,e_num=0,sizeof(hd));
for(int i=1;i<=m;i++)
{
while(a[i]+p[i]<=b[i]&&c[i]+p[i]<=d[i]&&find(a[i]+p[i])==find(c[i]+p[i]))
++p[i];
if(a[i]+p[i]>b[i])
{
if(d[i]-c[i]<=b[i]-a[i])
return puts("No"),0;
}
else if(c[i]+p[i]>d[i])
return puts("No"),0;
else
add_edge(find(a[i]+p[i]),find(c[i]+p[i]));
}
}
puts("Yes");
}