题解：AT_arc190_a [ARC190A] Inside or Outside
KarmaticEnding
·
·
题解
以此纪念我唯一一场 ARC 唯一一道做出来的题。
思路
题意不再赘述。我们把输出的第一行，也就是“代价”，叫做 cost。我们按照 cost 从小到大讨论。
首先，如果 cost=1，那么必然有一个区间满足 l=1,r=n，除此以外不会有其它 cost=1 的情况。
其次，我们特判一堆 cost=2 的情况。如果有两个区间 [l_1,r_1] 和 [l_2,r_2] 满足：
现在只剩一个 cost=3 的情况了。排除了前面所有情况之后，剩下的区间按照左端点排序，必然像这样：
我们把这些区间从上到下标号为 1,2,...,m。我们发现，只要对 1 号区间进行 1 操作，2 号区间进行 2 操作，m 号区间进行 1 操作，那么所有点都可以被覆盖到，就像这样：
发现 2 区间外每一个点都被覆盖到了，区间内的每一个点也都被覆盖到了。
这就是 cost=3 的情况。欸，那什么时候无解呢？在理论 cost=3 的情况中，如果 m=2，那么只有两个相交但不包含的区间，这时无论对这两个区间怎么操作都是无法覆盖整个序列的，所以无解。
代码实现
$cost=2$ 的情况，我们先把区间按照左端点排序，那么如果 $r_1<l_m$，就变成了 $cost=2$ 的第一种情况。
考虑一下怎么判断包含。还记得我们是怎么判断二维偏序的吗？对于 $(l_1,r_1),(l_2,r_2),\dots,(l_k,r_k)$，我们先按照 $l$ 排序，然后依次把 $r_1,r_2,\dots,r_k$ 加到树状数组中。这次我们先把区间排序了，然后我们把二维偏序反过来做，依次把 $r_m,r_{m-1},\dots,r_1$ 加入树状数组中来判断包含关系。这样就判掉了第二种情况。
除去这两种情况以后，区间 $1$ 和区间 $m$ 肯定是相交而不包含的关系，所以如果 $l_1=1,r_m=n$，就变成了第三种情况。
剩下的就是 $cost=3$ 的情况了，只用判断一个 $m\le 2$ 就可以了。
### 示例代码
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=2e5+10;
int n,m;
struct INTERVAL{
int l,r;
int id;
}a[MAXN];
namespace BIT{
int c[MAXN<<3];
#define lowbit(x) (x)&(-(x))
void add(int x){
while(x<=n){
++c[x];
x+=lowbit(x);
}
}
int query(int x){
int res=0;
while(x){
res+=c[x];
x-=lowbit(x);
}
return res;
}
}
using BIT::query;
using BIT::add;
inline int check_inside(){
for(int i=m;i>=1;--i){
if(query(a[i].r)){
return i;//返回:包含其他区间的区间是哪个区间
}
add(a[i].r);
}
return 0;
}
int ans[MAXN];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d",&a[i].l,&a[i].r);
a[i].id=i;
if(a[i].l==1&&a[i].r==n){
putchar('1');putchar('\n');//cost=1的情况
for(int j=1;j<=m;++j){
j==i?putchar('1'):putchar('0');
putchar(' ');
}
return 0;
}
}
sort(a+1,a+m+1,[&](INTERVAL H,INTERVAL G){return H.l==G.l?H.r<G.r:H.l<G.l;});
if(a[1].r<a[m].l){//两个区间相互分离
putchar('2');putchar('\n');ans[a[1].id]=2;
ans[a[m].id]=2;
}
else{
int p=check_inside();
if(p){//存在区间相互包含的情况
bool flag=false;
putchar('2');putchar('\n');
for(int i=1;i<=m;++i){
if(i==p){
ans[a[i].id]=1;
}
else if((!flag)&&(a[i].l>=a[p].l&&a[i].r<=a[p].r)){
ans[a[i].id]=2;
flag=true;
}
}
}
else{
if(a[1].l==1&&a[m].r==n){
putchar('2');putchar('\n');ans[a[1].id]=1;
ans[a[m].id]=1;
}
else{
if(m<=2){
putchar('-');putchar('1');
return 0;
}
else{
putchar('3');putchar('\n');
ans[a[1].id]=1;
ans[a[2].id]=2;
ans[a[m].id]=1;
}
}
}
}
for(int i=1;i<=m;++i){
putchar(ans[i]|'0');putchar(' ');
}
return 0;
}
```