(mathcal{Description})
给定排列 ({a_n})，求字典序第 (K) 大的合法排列 ({b_n})。称一个排列 ({p_n}) 合法，当且仅当依次将 ([1,m],[2,m+1],cdots,[n-m+1,n]) 内的 (p) 升序排列后，得到的排列为 ({a_n}) 相同。
(nle2 imes 10^6)，(mle 100)，(Kle2 imes 10^{16}) 。
(mathcal{Solution})
应该说是构造题吧，想到几乎所有结论却打不出分 qwq。
显然，(b_i) 在 ({a_n}) 中的下标属于集合 ([max{1,i-m+1},n])，反过来，(a_i) 在 ({b_n}) 中对应的下标属于集合 ([1,min{i+m-1,n}])。
然后可以发现 ({a_n}) 中的逆序对非常特殊。有性质：
归纳证明。考虑一对 ((i,j))，满足 (max_{kin(i,j)}{a_k}<a_j<a_i)，若 (i+1=j)，显然；否则对于 (kin(i,j))，已有 (b_{k+m-1}=a_k)，不妨设 (b_x=a_j)，则 (x otin[i+m,j+m-2])，而 (xin[1,min{j+m-1,n}])，又有 (xge i+m)，所以 (x=j+m-1) 成立。
所以可以直接确定所有存在逆序对的 (j) 的位置。接下来考虑 ({a_n}) 是一个单增排列的情况。
从左往右构造 ({b_n})，我们需要求出固定 ({b_n}) 的前缀时所有合法 ({b_n}) 的方案数。不妨设固定前 (i) 位，对于一个没有出现的 (a_j)，其放置方案数显然为 (min{j+m-1,n}-i)。乘法原理就可以得到所求，最后类似多叉树求第 (K) 大地枚举就好，复杂度 (mathcal O(n^3))。
由于方案数是指数增长，所以前面很多位直接从小到达钦定，再对后缀的 (mathcal O(log_mn)) 暴力构造即可。
复杂度 (mathcal O(n+log^3n))。
(mathcal{Code})
/* Clearink */
#include <cstdio>
#include <algorithm>
typedef long long LL;
inline LL rint () {
LL x = 0; char s = getchar ();
for ( ; s < '0' || '9' < s; s = getchar () );
for ( ; '0' <= s && s <= '9'; s = getchar () ) x = x * 10 + ( s ^ '0' );
return x;
}
template<typename Tp>
inline void wint ( Tp x ) {
if ( x < 0 ) putchar ( '-' ), x = ~ x + 1;
if ( 9 < x ) wint ( x / 10 );
putchar ( x % 10 ^ '0' );
}
inline int min_ ( const int a, const int b ) { return a < b ? a : b; }
const int MAXN = 2e6;
int n, m, a[MAXN + 5];
LL K;
int top, stk[MAXN + 5], ans[MAXN + 5];
bool used[MAXN + 5];
inline void setnxt ( int& pos, const int x ) { for ( ; ans[pos]; ++ pos ); ans[pos] = x; }
int main () {
freopen ( "gift.in", "r", stdin );
freopen ( "gift.out", "w", stdout );
n = rint (), m = rint (), K = rint ();
for ( int i = 1; i <= n; ++ i ) a[i] = rint ();
for ( int i = 1; i <= n; ++ i ) {
if ( a[i] < a[stk[top]] ) ans[i + m - 1] = a[i];
else stk[++ top] = i;
}
int mut = top, pos = 1;
for ( LL all = 1; mut && all < K; -- mut ) {
all *= min_ ( m, top - mut + 2 );
}
for ( int i = 1; i < mut; ++ i ) setnxt ( pos, a[stk[i]] );
for ( int i = mut; i <= top; ++ i ) {
for ( int j = mut; j <= top; ++ j ) {
if ( used[j] ) continue;
used[j] = true;
LL all = 1;
for ( int k = mut, pre = i; k <= top; ++ k ) {
if ( !used[k] ) {
all *= min_ ( top, k + m - 1 ) - pre ++;
}
}
if ( all < K ) K -= all, used[j] = false;
else { setnxt ( pos, a[stk[j]] ); break; }
}
}
for ( int i = 1; i <= n; ++ i ) {
wint ( ans[i] );
putchar ( i ^ n ? ' ' : '
' );
}
return 0;
}