AtCoder Regular Contest 165

https://atcoder.jp/contests/arc165

D - Substring Comparison

题意

给定一个长度为 $n$ 的序列 $x$，给出 $m$ 组限制。每组限制 $(a_i,b_i,c_i,d_i)$ 表示 $x_{a_i,a_{i+1},\cdots,b_i}$ 的字典序小于 $x_{c_i,c_{i+1},\cdots,d_i}$。判断是否存在一个序列 $x$ 满足所有的限制条件。

数据范围：$2\leq n\leq 2000,1\leq m\leq 2000$。

题解

我们依次考虑每一个限制条件，如果 $a_i$ 和 $c_i$ 相等，那么考虑 $a_{i+1},c_{i+1}$，直到不相等或超过了 $b_i$ 或 $d_i$。如果超过了 $d_i$，那么无解。如果超过了 $b_i$，那么该限制一定可以被满足。考虑 $a_i$ 和 $c_i$ 不等的情况，此时 $a_i$ 向 $c_i$ 连边，由此可以得到一张图。如果这张图里没有环，那么一定有解。否则，将一个强连通分量内的所有数都置成最小的数（只要是相同的数就可以，序列 $x$ 中这些位置上的数一定都相等）。然后重复上述过程。由于每次循环至少减少一个不同的数，一共有 $n$ 个数，所以循环次数是 $O(n)$ 的。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=2005;
int n,m,cnt,a[N],b[N],c[N],d[N],f[N],head[N],col[N],mn[N];
bool flag[N],vis[N];
vector<int> g[N],g2[N];
stack<int> s;
int find(int x) {return f[x]==x?x:f[x]=find(f[x]);}
void merge(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y) return;
    f[x]=y;
}
void dfs1(int u)
{
    vis[u]=1;
    for(auto v:g[u])
        if(!vis[v]) dfs1(v);
    s.push(u);
}
void dfs2(int u)
{
    col[u]=cnt;
    mn[cnt]=min(mn[cnt],u);
    for(auto v:g2[u])
        if(!col[v]) dfs2(v);
}
void kosaraju()
{
    cnt=0;
    for(int i=1;i<=n;i++)
        if(!vis[i]&&find(i)==i) dfs1(i);
    while(!s.empty())
    {
        int u=s.top();s.pop();
        if(!col[u])
        {
            cnt++;
            dfs2(u);
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) f[i]=i;
    for(int i=1;i<=m;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];
    while(1)
    {
        for(int i=1;i<=n;i++) vis[i]=0,col[i]=0,mn[i]=0x3f3f3f3f,g[i].clear(),g2[i].clear();
        for(int i=1;i<=m;i++)
        {
            if(flag[i]) continue;
            while(a[i]+head[i]<=b[i]&&c[i]+head[i]<=d[i]&&find(a[i]+head[i])==find(c[i]+head[i])) head[i]++;
            if(c[i]+head[i]>d[i])
            {
                cout<<"No"<<'\n';
                return 0;
            }
            if(a[i]+head[i]>b[i])
            {
                flag[i]=1;
                continue;
            }
            g[find(a[i]+head[i])].push_back(find(c[i]+head[i]));
            g2[find(c[i]+head[i])].push_back(find(a[i]+head[i]));
        }
        kosaraju();
        bool ok=1;
        for(int i=1;i<=n;i++)
        {
            if(find(i)!=i) continue;
            if(mn[col[i]]!=i)
            {
                merge(i,mn[col[i]]);
                ok=0;
            }
        }
        if(ok)
        {
            cout<<"Yes"<<'\n';
            return 0;
        }
    }
    return 0;
}