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;
}