【题解】CF1348F Phoenix and Memory
wsyhb
·
·
题解
题意简述
问是否存在唯一的长度为 n 的排列 p，满足 a_i \le p_i \le b_i \; (1 \le i \le n)。
数据保证至少存在一个符合题意的排列。
如果唯一，输出这个排列；否则输出任意两种不同的满足题意的排列。
数据范围：1 \le n \le 2 \times 10^5
分析 + 题解
首先考虑如何求出一个可行的排列。
事实上，这可以转化为一个简单的贪心问题——
具体实现可以**把线段按左端点排序**，然后从小到大枚举 $i$，对于每个 $i$，先将左端点为 $i$ 的线段丢进堆（优先队列）里，然后从中**取出右端点最小的线段**，与 $i$ 号点匹配即可。
由于我们在讨论 $i$ 号点之前，所有包含 $i$ 号点且未匹配的线段均在堆中，因此我们贪心选取其中右端点最小的策略是正确的。
（右端点越靠右，这条线段就有越多的选择的机会）
那么如何求出另外一个满足题意的排列呢？（或者发现无解）
------------
引理：**若存在另外一个满足题意的排列，我们一定可以通过交换已知排列中的其中两个数来转化成它。**
证明：
在上述条件下，必然存在一个长度 $\ge 2$ 的循环。（这是修改排列以保证仍然满足题意的充要条件）接下来让我们证明必然存在一个长度 $=2$ 的循环。
假设不存在长度 $=2$ 的循环，则必然存在一个**最短的**长度 $\ge 3$ 的循环。
设 $y$ 为这个循环中最左边的一个点，$x$ 是 $y$ 的前驱，$z$ 是 $y$ 的后继（即 $y$ 可以改为匹配 $x$ 当前对应的线段，$z$ 可以改为匹配 $y$ 当前对应的线段），如图所示：
请注意 $y$ 当前对应线段的右端点一定在 $x$ 左侧，否则 $x$ 和 $y$ 就会形成一个长度为 $2$ 的循环。
而我们可以发现，此时移除 $y$ 没有任何影响，因为 $z$ 可以改为匹配 $x$ 当前对应的线段。于是我们可以获得一个更小的环，这与假设矛盾，故引理成立。
------------
于是我们只需要求出需要交换的 $p_i$ 和 $p_j$，以满足 $a_i \le p_j \le b_i$，且 $a_j \le p_i \le b_j$。
不妨设 $p_i < p_j$，则条件转化为 $a_j \le p_i < p_j \le b_i$。枚举 $i$，发现只需查询是否存在 $j$ 满足 $a_j \le p_i$（$p_i$ 为定值）且 $p_i < p_j \le b_i$（$p_i,b_i$ 为定值）。
我们设 $id$ 为 $p$ 的逆映射，即 $id_{p_i}=i$，将 $i$ 的枚举顺序改为 $id_1$，$id_2$，$\cdots$，$id_n$，每次先把 $a_j=p_i$ 的 $j$ 对应的 $p_j$ 扔进 set，然后查询 set 中是否存在值 $\in (p_i,b_i]$，二分查找即可。
## 代码
查询方法见注释。
``` cpp
#include<bits/stdc++.h>
using namespace std;
const int max_n=2e5+5;
struct node
{
int a,b,id;
}c[max_n];
vector<node> v[max_n];
inline bool operator > (const node &x,const node &y)//重载运算符以在小根堆中比较
{
return x.b>y.b;
}
priority_queue<node,vector<node>,greater<node> > q;
int p[max_n],id[max_n];
set<int> s;
set<int>::iterator it;
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i)
{
scanf("%d%d",&c[i].a,&c[i].b);
c[i].id=i;
v[c[i].a].push_back(c[i]);//把 c[i] 丢进左端点编号对应的 vector 中
}
for(int i=1;i<=n;++i)
{
for(int j=0;j<int(v[i].size());++j)
q.push(v[i][j]);//先加入
id[i]=q.top().id;//再取出
p[id[i]]=i;
q.pop();
}
for(int x=1;x<=n;++x)
{
for(int j=0;j<int(v[x].size());++j)
s.insert(p[v[x][j].id]);//先加入
int i=id[x];//枚举 x 获得对应 i
it=s.upper_bound(x);//再查询
if(it!=s.end()&&*it<=c[i].b)
{
int j=id[*it];
puts("NO");
for(int k=1;k<=n;++k)
printf("%d%c",p[k],k<n?' ':'\n');
swap(p[i],p[j]);
for(int k=1;k<=n;++k)
printf("%d%c",p[k],k<n?' ':'\n');
return 0;
}//查询方法：二分找到大于 p[i] 的第一个数，判断其是否小于等于 b[i]
}
puts("YES");
for(int k=1;k<=n;++k)
printf("%d%c",p[k],k<n?' ':'\n');
return 0;
}
```