ARC165D Substring Comparison
樱雪喵
·
·
题解
Description
构造一个长度为 n 的整数序列 X，使其满足 m 条限制。第 i 条限制形如 (A_i,B_i,C_i,D_i)，表示要求 X 的子段 [A_i,B_i] 字典序小于 [C_i,D_i]。问是否存在满足条件的序列 X。
## Solution
对于 $A_i=C_i$ 的询问，可以直接比较 $B_i$ 和 $D_i$ 的大小，$B_i>D_i$ 则无解，否则这个限制一定满足，可以忽略。因此，我们假设所有询问满足 $A_i\neq C_i$。
我们希望每组限制的两个区间在尽量靠前的位置上就开始不一样，因为这样后面的位就都没有大小限制。看到判断若干点之间的大小关系能否满足，考虑建图。
对每组限制连边 $A_i\to C_i$，表示对于 $X$ 有限制 $X_{A_i}\le X_{C_i}$。那么连出的这个图分两种情况：
- 图里没有环，则直接按拓扑序给 $X$ 的每个位置赋值即可，答案为 `Yes`。
- 图里有环，需要做进一步考虑。
对于在同一个强连通分量内的点，要满足图连边的大小关系，它们的 $X$ 值必须都相等。因此可以对这个图跑 tarjan 求出强连通分量，并重新依次考虑题目给出的每个限制：
- 如果 $A_i$ 和 $C_i$ 不在一个强连通分量，那么它们所在位置的 $X$ 值不相等，这个字典序的条件已经满足了；
- 否则，代表 $X_{A_i}$ 和 $X_{C_i}$ 一定是相等的，需要限制它们下一位的大小关系。我们令 $A_i\gets A_i+1,C_i\gets C_i+1$，并在缩点后的图上重新建图，重复以上步骤。
- 如果一直重复到 $A_i=B_i$ 或 $C_i=D_i$ 它们都只能相等，判断哪个区间还剩下一段，如果是前面的区间剩一段就无解。否则这个限制已经满足。
如果重复完了上述步骤，中途没有被判无解，就是有解。
每次重复该过程都会让当前未满足限制的 $A_i\gets A_i+1$，至多重复 $n$ 次。每次跑一个 tarjan，复杂度 $O(n+m)$。总复杂度 $O(n^2+nm)$。
代码为了好写用并查集维护了哪些点值相等，但这不是复杂度瓶颈。
```cpp
const int N=2005;
int n,m,fa[N];
int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}
il void merge(int x,int y) {if(find(x)!=find(y)) fa[find(x)]=find(y);}
struct edge{int nxt,to;}e[N<<1];
int head[N],cnt;
il void add(int u,int v) {e[++cnt]={head[u],v};head[u]=cnt;}
int dfn[N],low[N],in[N],tot;
stack<int> Q;
bool flag;
void tarjan(int u)
{
dfn[u]=low[u]=++tot,in[u]=1; Q.push(u);
for(int i=head[u];i;i=e[i].nxt)
{
int v=e[i].to;
if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]);
else if(in[v]) low[u]=min(low[u],dfn[v]);
}
if(dfn[u]==low[u])
{
while(!Q.empty())
{
int t=Q.top(); if(t!=u) flag=1;
merge(t,u),in[t]=0,Q.pop();
if(t==u) break;
}
}
}
il void clear()
{
memset(head,0,sizeof(head)),cnt=0;
memset(dfn,0,sizeof(dfn)),memset(low,0,sizeof(low)),tot=0;
}
struct node{int a,b,c,d;} q[N];
int main()
{
n=read(),m=read();
for(int i=1;i<=m;i++) q[i]={read(),read(),read(),read()};
for(int i=1;i<=n;i++) fa[i]=i;
for(int w=1;w<=n;w++)
{
clear();
for(int i=1;i<=m;i++)
{
while(find(q[i].a)==find(q[i].c)&&q[i].a<=q[i].b&&q[i].c<=q[i].d)
q[i].a++,q[i].c++;
if(q[i].c>q[i].d) {printf("No\n");return 0;}
if(q[i].a<=q[i].b) add(find(q[i].a),find(q[i].c));
}
flag=0;
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
if(!flag) break;
}
printf("Yes\n");
return 0;
}
```