Solutions CS101

Appearance

27699: Wide Swap ​

http://cs101.openjudge.cn/practice/27699/

给出一个元素集合为 {1,2,…,N} (1≤N≤500,000) 的排列 P，当有 i,j (1≤i<j≤N) 满足 j−i≥K (1≤K≤N−1) 且 |Pi−Pj|=1时，可以交换 Pi 和 Pj。

求：可能排列中字典序最小的排列。

输入

N K

输出

P1 P2 ... PN

样例输入

sample1 input:
4 2
4 2 3 1

sample1 output:
2
1
4
3

解释：4 2 3 1  -  4 1 3 2  -  3 1 4 2  -  2 1 4 3 

sample2 input:
5 1
5 4 3 2 1

sample2 output:
1
2
3
4
5

样例输出

sample3 input:
8 3
4 5 7 8 3 1 2 6

sample3 output:
1
2
6
7
5
3
4
8

提示

约束

$ 2≦N≦500,000 $

$ 1≦K≦N-1 $

$ P $ 是$ 1,\ 2,\ ...,\ N $ 的排列。

来源: https://www.luogu.com.cn/problem/AT_agc001_f

c++
// https://www.cnblogs.com/PinkRabbit/p/AGC001F.html
#include <cstdio>
#include <algorithm>
#include <queue>

const int Inf = 0x3f3f3f3f;
const int MN = 500005, MS = 1 << 20 | 7;

int N, K, P[MN], Ans[MN];

#define li (i << 1)
#define ri (li | 1)
#define mid ((l + r) >> 1)
#define ls li, l, mid
#define rs ri, mid + 1, r
int mxp[MS];
void Build(int i, int l, int r) {
	if (l == r) return mxp[i] = l, void();
	Build(ls), Build(rs);
	mxp[i] = P[mxp[li]] > P[mxp[ri]] ? mxp[li] : mxp[ri];
}
void Del(int i, int l, int r, int p) {
	if (l == r) return mxp[i] = 0, void();
	p <= mid ? Del(ls, p) : Del(rs, p);
	mxp[i] = P[mxp[li]] > P[mxp[ri]] ? mxp[li] : mxp[ri];
}
int Qur(int i, int l, int r, int a, int b) {
	if (r < a || b < l) return 0;
	if (a <= l && r <= b) return mxp[i];
	int v1 = Qur(ls, a, b), v2 = Qur(rs, a, b);
	return P[v1] > P[v2] ? v1 : v2;
}

int inq[MN];
std::priority_queue<int> pq;
inline void check(int id) {
	if (inq[id]) return ;
	if (Qur(1, 1, N, id - K + 1, id + K - 1) == id)
		pq.push(id), inq[id] = 1;
}

int main() {
	scanf("%d%d", &N, &K);
	for (int i = 1; i <= N; ++i) scanf("%d", &P[i]);
	P[0] = -Inf;
	Build(1, 1, N);
	for (int i = 1; i <= N; ++i) check(i);
	for (int i = N; i >= 1; --i) {
		int u = pq.top(); pq.pop();
		Ans[u] = i;
		Del(1, 1, N, u);
		int pos;
		if ((pos = Qur(1, 1, N, u - K + 1, u - 1))) check(pos);
		if ((pos = Qur(1, 1, N, u + 1, u + K - 1))) check(pos);
	}
	for (int i = 1; i <= N; ++i) printf("%d\n", Ans[i]);
	return 0;
}