AtCoder 080E Young Maids

AtCoder 080E Young Maids"/>

AtCoder 080E Young Maids

与题意相反，从左往右进行构造。
注意到对每一段区间[L, R]选取最小对{x, y}时，x必须处于与L同奇偶性的位子，而y必须处于与x奇偶性相反的位子。选取最小的x以及最小的y可以用两个RMQ维护原数组，奇偶各一个。
当选完一对{x, y}时，区间分裂为[L, pos[x]-1], [pos[x]+1, pos[y]-1], [pos[y]+1, R]三个区间，可以用优先队列进行BFS，保证字典序最小。

代码：

#include<bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define CLR(A, X) memset(A, X, sizeof(A))
using namespace std;typedef long long LL;
typedef pair<int, int> PII;
const double eps = 1e-10;
int dcmp(double x) {