CF1348F Phoenix and Memory 题解

题意：

cxy 有 $n$ 个朋友，朋友们的编号是 $1\sim n$。他的朋友们本来按某种特殊顺序排成一排，但 cxy 还没来得及按下快门，就有一只鸭子乱入，把原本排好的顺序搞得乱七八糟。

现在，cxy 不得不重新排好顺序，但他记不清了QAQ！他只记得从左数起的第 $i$ 个朋友的编号大小在 $a_i$ 和 $b_i$ 之间。该怎么办？他只好向你请教。请问根据他的记忆有没有唯一一种方法给他的朋友们排序？

形式化的，给定 $a_i,b_i$ ，问是否存在唯一长 $n$ 的排列 $p$ ，满足 $a_i \leq p_i \leq b_i$ 。

数据保证至少有一个符合题意的排列。

输入格式

第一行一个整数 $n~(1 \leq n \leq 2 \times 10^5)$，表示 cxy 的朋友数。

接下来 $n$ 行，第 $i$ 行两个整数 $a_i$ 和 $b_i~(1 \leq a_i \leq b_i \leq n)$ ，表示 cxy 对从左数第 $i$ 个朋友编号的记忆。

输出格式

如果存在唯一一个排列符合题意，输出 YES，然后换一行输出 $n$ 个整数，表示原本的排列。

否则，输出 NO，然后在接下来两行中输出任意两种不同的符合题意的排列，格式同上。若有多种答案，请输出任意一种。

这个题目有点绕脑筋的。

考虑构造一个合法的排列。我们将 $a_i$ 相同的 $(a_i,b_i)$ 放入一个 vector 内

接着枚举 $i$ ，每次将 $a_j=i$ 的 $(a_j,b_j)$ 放入一个优先队列，每次取出 $b_j$ 最小的那个填上 $i$ 。

形式化的，记第 $i$ 次取出来的 $(a,b)$ 编号为 $\mathrm{id}(i)$，令 $p_{\mathrm{id}(i)}\gets i$ ，答案即为 $p_i$ 。

注意到如果合法排列不唯一，那么当前排列必定存在至少一对 $p_i < p_j$ 的 $(i,j)$ 满足 $a_i\le p_j \le b_i$ 。

换句话说，只要存在这样的一对 $(i,j)$ ，我们交换 $i,j$ 即可得到另一组合法的排列。

考虑枚举 $p_i$，每次取出 $a_j = p_i$ 的 $j$ 扔进 set 里，然后查询 set 中是否存在 $p_j \in(p_i, b_i]$ ，set 里二分 $p_i$ 即可。

时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(2e5 + 15))

int id[N], p[N]; // id[i] 表示填了 i 的是哪个 (a, b)
struct node { int l, r, id; } a[N];
bool operator<(node x, node y){ return x.r > y.r; }
vector<node> vec[N]; priority_queue<node> q; set<int> s;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int n; cin >> n;
    rep(i, 1, n)
    {
        cin >> a[i].l >> a[i].r;
        a[i].id = i; vec[a[i].l].push_back(a[i]);
    }
    rep(i, 1, n)
    {
        for(auto j : vec[i]) q.push(j);
        p[id[i] = q.top().id] = i; q.pop();
    }
    rep(v, 1, n)
    {
        for(auto j : vec[v]) s.insert(p[j.id]);
        const int i = id[v]; auto it = s.upper_bound(v);
        if(it != s.end() && *it <= a[id[i]].r)
        {
            cout << "NO" << '\n';
            rep(k, 1, n) cout << p[k] << " \n"[k == n];
            swap(p[i], p[id[*it]]);
            rep(k, 1, n) cout << p[k] << " \n"[k == n];
            return 0;
        }
    }
    cout << "YES" << '\n';
    rep(i, 1, n) cout << p[i] << " \n"[i == n];
    return 0;
}