ARC165D Substring Comparison 做题记录

给定两个正整数 $n,m$ 以及 $m$ 组限制 $l1_i,r1_i,l2_i,r2_i$，求是否存在一个长 $n$ 的序列 $a$ 满足 $\forall 1\le i\le m$ 都有 $a_{[l1_i,r1_i]}$ 的字典序严格小于 $a_{[l2_i,r2_i]}$。

$1\le n,m\le 2\times 10^3$。

比较巧妙的建模题。

对于每个限制，先考虑其第一个字符的大小关系，显然有 $a_{l1_i}\le a_{l2_i}$。考虑建出一个 $n$ 个点的图 $G$，对于第 $i$ 个限制，从 $l1_i$ 向 $l2_i$ 连一条有向边表示它们的大小关系。

那么不难发现 $G$ 中同一个强连通分量中的点对应位置上的字符是相同的。那么不妨把 $G$ 缩点。缩点后对于第 $i$ 个限制，设 $a_{[l1_i,r1_i]}$ 和 $a_{[l2_i,r2_i]}$ 长 $st_i$ 前缀已知相同，那么让 $l1_i$ 和 $l2_i$ 均加上 $st_i$，即可转化为子问题。

无解当且仅当某一时刻某条限制 $i$ 满足 $l1_i+st_i\le r1_i$ 且 $l2_i+st_i> r2_i$，有解则当且仅当这个过程可以不断进行下去，不难发现只有前 $n$ 次缩点是有效的。

时间复杂度 $O(n^2)$。

代码如下：

// Problem: [ARC165D] Substring Comparison
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/AT_arc165_d
// Memory Limit: 1 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int S=2005;

struct node
{
	int l1,r1,l2,r2;
}a[S];

int n,m;
int fa[S];
vector<int> g[S];
int cnt,dfn[S],low[S];
int top,sta[S];
bool vis[S],inst[S];

int fnd(int x)
{
	return fa[x]==x?x:fa[x]=fnd(fa[x]);
}

void dfs(int u)
{
	low[u]=dfn[u]=++cnt;
	vis[u]=true;
	sta[++top]=u;
	inst[u]=true;
	for(int v:g[u])
	{
		if(!vis[v]) dfs(v),low[u]=min(low[u],low[v]);
		else if(inst[v]) low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u])
	{
		while(1)
		{
			int v=sta[top--];
			fa[fnd(v)]=fnd(u);
			inst[v]=false;
			if(v==u) break;
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d%d",&a[i].l1,&a[i].r1,&a[i].l2,&a[i].r2);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++) g[a[i].l1].push_back(a[i].l2);
	for(int T=1;T<=n;T++)
	{
		cnt=0;
		for(int i=1;i<=n;i++) vis[i]=inst[i]=false;
		top=0;
		for(int i=1;i<=n;i++) if(!vis[i]) dfs(i);
		for(int i=1;i<=n;i++) g[i].clear();
		for(int i=1;i<=m;i++)
		{
			int &l1=a[i].l1,&l2=a[i].l2;
			int r1=a[i].r1,r2=a[i].r2;
			while(l1<=r1&&l2<=r2&&fnd(l1)==fnd(l2)) l1++,l2++;
			if(l2>r2) return puts("No"),0;
			if(l1>r1) continue;
			g[fnd(l1)].push_back(fnd(l2));
		}
	}
	puts("Yes");
	return 0;
}