前言

看到题解里都是用标记来记录选择的，这篇题解用指针直接将数字放进最终数组。

题目描述

给定两个整数 ，构造一个排列使得恰好有 个二元组 ，满足 ，且 恰好为 的幂次。

解题思路

我们先假设排列是 ，显然这个排列没有满足的二元组。

考虑更改数的位置来增加满足要求的二元组数量。

数值 需满足 ，即逆序对，我们考虑将一个数往前放，来达到目的。

对于排列 的其中一个数 ，如果我们将 提到最前面，那么排列变成 ，新增二元组 个，由于差值需要恰好为 的幂次，所以满足要求的二元组增加了 个，即 。（ 是向下取整符号）

如果我们先提前 到最前面，然后提前 到最前面，需满足 ，那么会发现提前 新增的二元组不会受到 提前的影响，因此如果我们以数值从小到大顺序提前，那么可以独立计算每个数提前的贡献。

预处理或者实时计算 ，不难发现，如果 那么通过选择部分 可以使得 ，这是一个经典的贪心拼凑问题。（数论函数 的数值和比例小于等于 ，则一定可以通过求和拼凑出所有正整数）

接下来贪心从大到小顺序枚举 拼凑 ：

• 如果 ，那么将 统计进 。

• 否则不统计。

由于从大到小顺序枚举，因此在将数值提到前面时，不能提到最前面，而是上一次提前的数值后面（反过来从小往大顺序想，就是上一次提前的数值提到最前面）。并且不提前的数值应放在上一次不提前的数值前面。使用两个指针能够维护数值的放置。

时间复杂度 （实时计算 会有 ）。

代码实现：

#include<bits/stdc++.h>
#define ll long long
#define MXN 1000002
using namespace std;
#define rdc getchar
#define ptc putchar
inline void rd(ll &x){x=0;short f=1;char c=rdc();while((c<'0'||c>'9')&&c!='-') c=rdc();if(c=='-') f=-1,c=rdc();while(c>='0'&&c<='9') x=x*10+c-'0',c=rdc();x*=f;}
inline void pt(ll x,ll k=10){if(x<0) ptc('-'),x=-x;if(x>=k) pt(x/k,k);ptc(x%k+'0');}
ll T=1,n,k;
ll q[MXN],l,r;//最终数组与前后两个指针
ll f(ll x){//计算log2(x-1)
    ll num=0;--x;
    while(x) ++num,x>>=1;
    return num;
}
void solv(){
    rd(n),rd(k);
    l=0,r=n+1;
    for(ll i=n;i;--i)//这里 k 实时减掉 f(i)
        if(f(i)<=k) q[++l]=i,k-=f(i);//如果 f(i)<=k，则将 i 提前，放到数组前方 
        else q[--r]=i;//否则，则 i 不提前，放到数组后方
    if(k) pt(-1);//如果无法拼凑出 k，那么构造方案不存在
    else for(ll i=1;i<=n;++i)//否则，输出最后构造的排列
        pt(q[i]),ptc(' ');
}int main(){while(T--) solv();}