企业做推广哪些网站比较好/seo搜索引擎优化人才

题意：

　　给出a数组的排列。求出字典序第k小的b数组的排列，满足1<=b_i<=n，b_ii+1，a[b[i]]0。

题解：

　　用树状数组倒着求出以每个数为首的递增子序列个数。若总的个数之和小于k则输出-1。

　　总的个数可能非常大而k<=1e18。所以要判下上界。

　　最后从1~n扫一遍。当前数大于上一个加入答案的数时，若以它为首的递增子序列个数小于k，则用k减去那个个数，否则将这个数加入答案并将k-1（即减去后面不再加数的情况）。

　　k = 0时跳出循环。

#include 
using namespace std;
typedef long long ll;
const int N = 5e5+10;
const ll inf = 1e18+10;
int n, tot, pre;
ll k, sum;
int a[N], id[N], ans[N];
ll tre[N], val[N];
ll add(ll x, ll y) { return min(x + y, inf); }
void update(int pos, ll val) {while(pos > 0) {tre[pos] = add(tre[pos], val);pos -= pos&(-pos);}
}
ll query(int pos) {ll res = 0;while(pos <= n) {res = add(res, tre[pos]);pos += pos&(-pos);}return res;
}
int main() {scanf("%d%lld", &n, &k);for(int i = 1; i <= n; i++) {scanf("%d", &a[i]);id[i] = a[i];}sort(id+1, id+n+1);for(int i = n; i >= 1; i--) {int p = lower_bound(id+1, id+n+1, a[i])-id;val[i] = query(p+1)+1;update(p, val[i]);}for(int i = 1; i <= n; i++) sum = add(sum, val[i]);if(sum < k) {puts("-1");return 0;}for(int i = 1; i <= n; i++) {if(k == 0) break;if(a[i] <= a[pre]) continue;if(val[i] < k) k -= val[i];else {ans[++tot] = i;k--;pre = i;}}printf("%d\n", tot);for(int i = 1; i < tot; i++) printf("%d ", ans[i]);printf("%d\n", ans[tot]);
}

?

转载于:https://www.cnblogs.com/Pneuis/p/9420437.html