ARC 165 - F - Make Adjacent
Statement
给定一个长度为 \(2n\) 的数列 \(a\) ，其中对于每个数 \(i \in [1,n]\)，恰好在 \(a\) 中出现两次。每次可以将两个相邻的数交换。最后要求 \(\forall i \in [1,n] : a_{2i-1} = a_{2i}\)。
在满足操作次数最小的前提下，操作后的数列 \(a'\) 的字典序尽量小。
Constraints
- \(1 \le n \le 2 \times 10^5\)
- \(1 \le a_i \le n\)
- \(\forall i : \exists x,y\in [1,2n],x \ne y,a_x = a_y=i\)
Hint [1]
考虑如何让操作数最小，那么我们可以转为考虑一些数的相对位置是否有限制。
Hint [2]
考虑如何让操作数最小：
令 \(i\) 第一次出现的位置为 \(x_i\)，第二次出现的位置为 \(y_i\)。
有 \(i,j\in[1,n],i\ne j\)。
不妨设 \(x_i < x_j\)。
如果有 \(y_i < y_j\)，则仅关于 \(i,j\) 的交换：实现 \(j\) 在 \(i\) 前面的操作数 \(\ge 3\)，实现 \(i\) 在 \(j\) 前面的操作数 \(\le 1\)，这时答案中两个连续的 \(i\) 的位置只能在两个连续的 \(j\) 的前面。
如果有 \(y_i > y_j\)，则仅关于 \(i,j\) 的交换：实现 \(j\) 在 \(i\) 前面的操作数为 \(2\)，实现 \(i\) 在 \(j\) 前面的操作数为 \(2\)，这时答案中两个连续的 \(i\) 的位置和两个连续的 \(j\) 的相对位置任意。
故当前仅当 \(x_i < x_j \land y_i < y_j\) 时我们才需强制使最终 \(i\) 的位置在 \(j\) 的前面，否则相对位置可以随意。
或许将 \((x_i,y_i)\) 看作二维点对会更容易理解下文。
Hint [3-A]
我们可以考虑建图并拓扑排序，这样拓扑排序得到的字典序最小的拓扑序即为答案中的相对顺序。但是在建图的时候需要使用线段树维护，时间复杂度 \(\mathrm{O}(n\log_2{n})\)。（说实话这种做法具体我也不清楚）
Hint [3-B]
考虑到必须使用线段树，不如直接用线段树计算答案。
维护一个点集 \(S\)，表示当前可以直接放在当前序列末端的数。
那么我们每次在 \(S\) 中选择最小的数，然后用线段树更新 \(S\)，这样一定是答案。
Hint [3-B-\(\alpha\)]
\(S\) 中的数的性质：
设还没有放入答案序列的数的集合为 \(A\supseteq S\) 。
首先如果将 \(S\) 中的数 \(i\) 按照 \(x_i\) 从小到大排序记为 \(s_i\)，那么 \(y_{s_i}\) 一定单调递减。
然后我们在整个 \(A\) 中分析 \(S\) 的性质，这时我们发现 \(s_{i+1}\) 若存在则一定是 \(\forall j \in A,x_j > x_i\) 中最靠近 \(s_i\) 的 \(j\)。
Hint [3-B-\(\beta\)]
然后我们考虑若已知 \(A\) 如何求 \(S\)。
设计算时当前的 \(S\) 为 \(S'\)。
其实我们可以每次找到一个 \(i\) 满足 \(i\in A,i\notin S',y_i = \min \{y_j|j\in A,j \notin S',x_j < \min\{x_k|k \in S'\}\}\)，若找不到则说明 \(S=S'\)。
由 Hint [3-B-\(\alpha\)] 显然。
Summary
维护一个点集 \(S\)，表示当前可以直接放在当前序列末端的数。
每次在 \(S\) 中选择最小的数 \(s_i\) 删去，然后更新 \(S\)。（\(s_i\) 是 \(S\) 按 \(x\) 排好序的序列）
具体地，根据 Hint [3-B-\(\beta\)] 可知，可以在 \(x_j \in [x_{s_{i-1}} + 1 , x_{s_{i+1}}-1]\) 中的未选择的 \(j\) 进行 Hint [3-B-\(\beta\)] 的做法，注意 \(y_j\) 同时还要满足小于 \(y_{s_{i-1}}\)，当然显然不存在 \(x_j < x_{s_{i+1}}\)。
具体的更新参照部分代码：
void Add (int l, int r, int lt){ // lt 是区间中所有y不能超过的值，见上文。
while (l <= r){
int minn = Query (1, l, r); // 找到最小值。
if (minn >= lt) // 无法找到，退出。
return ;
inq[a[minn]] = true; // 更新 S
idx[x[a[minn]]] = true; // 更新 S
r = x[a[minn]] - 1; // 更新区间，满足 x 的条件。
Delete (1, x[a[minn]]); //在线段树中删除这个最小值。
}
}
Code
#include <bits/stdc++.h>
using namespace std;
#define N (n << 1)
#define lson(i) (i << 1)
#define rson(i) (i << 1 | 1)
const int inf = 5e8;
int n, a[400005], x[200005], y[200005], z[200005];
map < int , bool > inq, idx;
struct tree {
int l, r;
int value_min;
bool is_leaf;
void Clear (){
l = r = 0;
value_min = inf;
is_leaf = true;
}
tree (){
Clear ();
}
} tr[2000005];
void Setting (int p){
if (! tr[p].is_leaf)
tr[p].value_min = min (tr[lson (p)].value_min, tr[rson (p)].value_min);
}
void Build (int p, int l, int r){
tr[p].l = l;
tr[p].r = r;
if (l == r){
if (x[a[l]] == l)
tr[p].value_min = y[a[l]];
return ;
}
tr[p].is_leaf = false;
int mid = (l + r) >> 1;
Build (lson (p), l, mid);
Build (rson (p), mid + 1, r);
Setting (p);
}
int Query (int p, int l, int r){
if (tr[p].l >= l && tr[p].r <= r)
return tr[p].value_min;
int Res = inf, mid = (tr[p].l + tr[p].r) >> 1;
if (l <= mid)
Res = min (Res, Query (lson (p), l, r));
if (r > mid)
Res = min (Res, Query (rson (p), l ,r));
return Res;
}
void Delete (int p, int x){
if (tr[p].is_leaf){
tr[p].value_min = inf;
return ;
}
int mid = (tr[p].l + tr[p].r) >> 1;
if (x <= mid)
Delete (lson (p), x);
else
Delete (rson (p), x);
Setting (p);
}
void Add (int l, int r, int lt){
while (l <= r){
int minn = Query (1, l, r);
if (minn >= lt)
return ;
inq[a[minn]] = true;
idx[x[a[minn]]] = true;
r = x[a[minn]] - 1;
Delete (1, x[a[minn]]);
}
}
int main (){
scanf ("%d", &n);
for (int i = 1;i <= N;++ i){
scanf ("%d", &a[i]);
if (x[a[i]] == 0)
x[a[i]] = i;
else
y[a[i]] = i;
}
Build (1, 1, N);
Add (1, N, inf);
while (! inq.empty ()){
int i = inq.begin ()->first;
inq.erase (inq.begin ());
idx.erase (x[i]);
Delete (1, x[i]);
int l = 0, r = N + 1;
map < int , bool > :: iterator it = idx.upper_bound (x[i]);
printf ("%d %d ", i, i);
if (it != idx.end ())
r = it->first;
if (it != idx.begin ()){
-- it;
l = it->first;
}
Add (l + 1, r - 1, (l == 0) ? inf : y[a[l]]);
}
puts ("");
return 0;
}