题目描述

难度分:$1600$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$和$k(1 \leq k \leq 10^{12})$。

考虑$1$~$n$的一个排列$p$。计算$p$的所有非空连续子数组的最小值的和，记作$S(p)$。在所有$1$~$n$的排列中，设$S(p)$的最大值为$maxS$。

对于所有满足$S(p)=maxS$的排列$p$，输出其中字典序第$k$小的排列$p$。如果满足$S(p)=maxS$的排列个数小于$k$，输出$-1$。

输入样例

6
3 2
3 3
4 11
4 6
6 39
7 34

输出样例

1 3 2 
2 3 1 
-1
2 4 3 1 
-1
2 3 4 5 7 6 1 

算法

贡献法+构造

对于任意一个排列$p$，利用贡献法，就可以知道$1$~$n$作为最小值时，对应子数组对$S$的贡献（主要考察某个数$x$作为最小值时，左边界和右边界分别可以延伸多源）。

要想$S$最大，肯定就希望小的数字贡献小，这样大的数字贡献就会大（因为子数组的总数是确定的）。先考虑$1$，如果$1$在$1$和$n$两个端点位置，就有$n$个子数组为答案贡献$1$；但如果$1$在中间某个位置$x$，那就有$x \times (n-x+1) \gt n$个子数组为$S$产生$1$的贡献。这是我们不希望看到的，因此$1$~$n$，每次尽量让数字填在两端，除了最后一个$n$，其他每个数字都有两种填法，因此$S=maxS$总共有$2^{n-1}$个排列，如果$2^{n-1} \lt k$就无解。

然后$l=1$，$r=n$开始填数。如果未填数的排列数$\lt k$，就把当前要填的数$cur$填在$r$位置，$r$指针左移；否则将$cur$填在$l$位置，$l$指针右移。注意$2^{n-1}$是很大的，每填一个数自由度都要除以$2$，我们只维护指数的变化就可以了，每填一个数指数就减去$1$。

复杂度分析

时间复杂度

填的数字从$1$增长到$n$，且在填数的过程就是双指针算法，左右指针$l$和$r$都不会回退，因此时间复杂度为$O(n)$。

空间复杂度

整个过程中只使用了有限几个变量，额外空间复杂度为$O(1)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int t, n, a[N];
LL k;

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d%lld", &n, &k);
        bool ok = true;
        if(n < 50 && (1LL<<n - 1) < k) ok = false;
        if(!ok) {
            puts("-1");
        }else {
            int l = 1, r = n, cur = 1, p = n - 2;
            while(p >= 0) {
                if(p <= 50 && k > (1LL<<p)) {
                    a[r--] = cur++;
                    k -= 1LL<<p;
                }else {
                    a[l++] = cur++;
                }
                p--;
            }
            while(cur <= n) {
                a[l++] = cur++;
            }
            for(int i = 1; i <= n; i++) {
                printf("%d ", a[i]);
            }
            puts("");
        }
    }
    return 0;
}