初看以为是网络流，再一想复杂度不够，看了题解才发现是这样！

Posted on | In

https://codeforces.com/problemset/problem/1348/F

题目大意，一队人排队，每个人能安排连续的一段位置[a,b]，问安排的方案是否唯一，如果不唯一，任意输出两种。

第一眼看上去直接用dinic求二分图匹配，然后发现数据量是2e5，感觉不太够，并且判唯一也不好做。看了题解发现这类问题其实有贪心的方案的。

我们首先目标是找出任一组合理安排，从1到n遍历位置安排人选，安排哪个人呢？a位于当前位置或左边，且b最小的那个。这样的人目前是最急需安排的，这种方案如果不行，那么就无法安排了。最小b可以通过一个multiset维护。同时我们不用担心这个最小b会比i小，因为前面已经安排了i-1个，如果第i大的b比i小则说明没有合法方案。

这样一来就找到了合法安排方案，接下来研究是否能找到第二种。我们可以证明，如果存在不止一种安排方案，那么必然有一种是仅仅交换两个人。可以交换两个人需要满足什么条件呢？设i和j可交换且posi<posj，那么需要aj<=posi&&posi<posj<=bi。这个条件很容易理解。具体实现可以通过线段树维护位置区间上a的区间最小值（依据第一种合法方案），每次仅需查询位于i+1,b区间上的人的a最小值，如果比i小，就说明它可以和i位置的人交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include<bits/stdc++.h>
using namespace std;

#define ll long long
const int maxn=2e5+2;
#define lson (o<<1)
#define rson (o<<1|1)
struct node1{
    int a,b,id;
    node1(){}
    node1(int _a,int _b,int _id):a(_a),b(_b),id(_id){}
    friend bool operator<(node1 x,node1 y){
        return x.a<y.a;
    }
}ns1[maxn],ns2[maxn];
struct node2{
    int b,id;
    node2(){}
    node2(int _b,int _id):b(_b),id(_id){}
    friend bool operator<(node2 x,node2 y){
        return x.b<y.b;
    }
};

int match[maxn],rnk[maxn];
int n;

int val[maxn<<2];   //存区间a的最小值
void build(int o,int l,int r){
    if(l==r){
        val[o]=ns2[rnk[l]].a;
        return ;
    }
    int mid=(l+r)/2;
    build(lson,l,mid);
    build(rson,mid+1,r);
    val[o]=min(val[lson],val[rson]);
}
int query(int o,int l,int r,int L,int R){
    if(l>=L&&r<=R){
        return val[o];
    }
    int mid=(l+r)/2;
    int res=1e9;
    if(L<=mid){
        res=min(res,query(lson,l,mid,L,R));
    }
    if(R>mid){
        res=min(res,query(rson,mid+1,r,L,R));
    }
    return res;
}

int main(){
    cin>>n;
    for(int i=1,a,b;i<=n;i++){
        cin>>a>>b;
        ns2[i]=ns1[i]=node1(a,b,i);
    }
    sort(ns1+1,ns1+n+1);
    multiset<node2> up;
    int p=1;
    for(int i=1;i<=n;i++){  //i是要待分配人的位置
        while(p<=n&&ns1[p].a<=i){
            up.insert(node2(ns1[p].b,ns1[p].id));
            p++;
        }
        auto it=up.begin();
        match[(*it).id]=i;  //match记录每个人去什么位置
        rnk[i]=(*it).id;       //rnk记录每个位置是谁
        up.erase(it);
    }
    bool f=true;
    int res[2]; //res记录哪两个位置上的人可以交换
    build(1,1,n);
    for(int i=1,b;i<n;i++){
        b=ns2[rnk[i]].b;
        if(b==i) continue;
        int tmp=query(1,1,n,i+1,b);
        if(tmp<=i){
            f=false;
            res[0]=i;
            for(int j=i+1;j<=b;j++){
                if(ns2[rnk[j]].a==tmp){
                    res[1]=j;
                    break;
                }
            }
            break;
        }
    }
    if(f){
        printf("YES\n");
        for(int i=1;i<=n;i++)
            printf("%d%c",match[i],(i==n?'\n':' '));
    }else{
        printf("NO\n");
        for(int i=1;i<=n;i++)
            printf("%d%c",match[i],(i==n?'\n':' '));
        swap(match[rnk[res[0]]],match[rnk[res[1]]]);
        for(int i=1;i<=n;i++)
            printf("%d%c",match[i],(i==n?'\n':' '));
    }
}