题解：AT_arc190_a [ARC190A] Inside or Outside

RAYMOND_7 · 2025-01-13 09:46:48 · 题解

感谢 @沉石鱼惊旋 指出开始判断区间包含出现的问题。

简要题意：选择最少的区间，每个区间自由选择覆盖 [l,r] 或 [1,l-1] \cup [r+1,n] ，要求覆盖全集 [1,n]。

容易发现有解则答案不超过 3 。

• 考虑答案为 1，这个只要判断 [1,n] 是否存在。

• 考虑答案为 2，只需要考虑 11, 12, 22 三种情况能否全覆盖，分别对应两个区间并集为全集，包含关系，完全不交，直接判断即可。

• 接下来若只有两个区间无解，否则所有区间有公共部分，可以选择右端点最小和左端点最大的向外覆盖，随便再选一个区间向内覆盖，容易发现一定可行。

// LUOGU_RID: 198258183
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <iostream>
#include <vector>
#include <queue>
#include <cassert>
#include <ctime>

using namespace std;

#define PII pair<int,int>
#define x first
#define y second
#define For(i, l, r) for(int i = l; i <= r; i ++)
#define Rep(i, l, r) for(int i = l; i >= r; i --)

bool START;

void in(int &x)
{
    char c = getchar(); int op = 1;
    while(c > '9' || c < '0') op *= (c == '-' ? -1 : 1), c = getchar();
    for(x = 0; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0'; x *= op;
}

const int N = 1e6 + 50;

int n, m, a[N], L[N], R[N], cf[N], f[N], id[N];
PII p[N];

void Out(){For(i,1,m)printf("%d ", f[i]);}

bool ENDPOS = 0;
int main()
{
    double chu = clock();
    in(n); in(m);
    For(i, 1, m) in(L[i]), in(R[i]), cf[L[i]] ++, cf[R[i]+1]--;
    For(i,1,n)cf[i]+=cf[i-1];
    int ok=0;
    For(i,1,m)if(L[i]==1&&R[i]==n)ok=i;
    if(ok){puts("1"); f[ok]=1;Out(); return 0;}
    For(i,1,m)p[i]={L[i],R[i]};
    int mr=R[1],ml=L[1];
    For(i,1,m)mr=min(mr,R[i]),ml=max(ml,L[i]);
    if(ml>mr)
    {
        puts("2");
        int x=0,y=0;For(i,1,m)if(R[i]==mr)x=i;else if(L[i]==ml)y=i;
        f[x]=f[y]=2;
        Out();
        return 0;}
    For(i,1,m)id[i]=i;
    sort(id+1,id+m+1,[](int x,int y){return p[x].x!=p[y].x?p[x].x<p[y].x:p[x].y>p[y].y;});//左端点相同右端点降序
    For(i,1,m-1)
    {
        int u=id[i],v=id[i+1];
        if(p[u].y>=p[v].y)
        {
            puts("2");f[u]=1;f[v]=2;
            Out();return 0;
        }
    }
    For(i,2,n)
    {
        if(R[i]==n)
        {
            puts("2");f[id[1]]=f[i]=1;Out();return 0;
        }
    }
    if(m<3){puts("-1");return 0;}
    puts("3");
    int x=0,y=0;For(i,1,m)if(R[i]==mr)x=i;else if(L[i]==ml)y=i;
    int z=1;while(z==x||z==y)z++;
    f[x]=f[y]=2;f[z]=1;
    Out();
    cerr << "Time = " << (clock() - chu) / CLOCKS_PER_SEC << endl;
    cerr << (&ENDPOS - &START) * 1.0 / 1024 / 1024 << endl; return 0;
}