原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round5-H.html
给定一个序列 a[1..n]，求下标字典序第 k 小的严格递增子序列
$1\leq n\leq 10^5, 0\leq k\leq 10^{18}$
树状数组。
我们首先考虑如何求出从每一个下标开始取序列，能得到多少个不同的严格递增子序列。可以倒着推，设当前推到 $i$ ，则 $ans[i]=1+\sum_\limits{n\geq j>i,a[j]>a[i]}ans[j]$ 。这个东西我们可以从后往前扫一遍数组，用树状数组维护。由于我们需要防止爆 $long\ long$ , 但是 $k$ 却在 $10^{18}$ 范围内，所以我们可以重定义加法：$add(a, b) = min(a + b, 10^{18}+1)$ 。但是这样的话我们就不能使用减法了，不能差分算区间和了。但是我们发现树状数组求的是一段后缀和，于是只需要把值域翻转一下就可以了。
接下来，我们需要求字典序第 $k$ 的序列。
先把无解判掉。
然后假设当前得到的序列最后一个数字在第 $i$ 个位置，是 $a_i$ 。首先当前序列本身就是一个满足条件的子序列。设下一个比 $a_i$ 大的 数为 $a_{j_1}$ 则（按照字典序）接下来 $ans[j_1]$ 个子序列的前缀序列为当前序列再加上 $a_{j_1}$ 。类似地，设 $a_{j_2}$ 为第二个比 $a_i$ 大的数，那么再接下来 $ans[j_2]$ 个子序列的前缀序列为当前序列在加上 $a_{j_2}$ ；对于 $j_i\cdots$ 类似……直到找到了 $k$ 对应的范围，就可以得到结果序列的下一个字母。这个每次直接暴力找就可以了，时间复杂度为 $O(n)$ 。然而菜鸡博主一开始傻逼了，去写主席树，写到天昏地暗才发现直接暴力找就可以了……
总时间复杂度 $O(n\log n)$ 。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=500005;
int n,a[N],Ha[N],m=1;
LL k,INF=1000000000000000000LL;
void HASH(){
sort(Ha+1,Ha+n+1);
for (int i=2;i<=n;i++)
if (Ha[i]!=Ha[i-1])
Ha[++m]=Ha[i];
}
LL c[N],ans[N];
void add(int x,LL d){
for (x=m+1-x+1;x<=m+1;x+=x&-x)
c[x]=min(c[x]+d,INF+1);
}
LL sum(int x){
LL ans=0;
for (x=m+1-x+1;x;x-=x&-x)
ans=min(ans+c[x],INF+1);
return ans;
}
vector <int> Ans;
int main(){
scanf("%d%lld",&n,&k);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]),Ha[i]=a[i];
HASH();
for (int i=1;i<=n;i++)
a[i]=lower_bound(Ha+1,Ha+m+1,a[i])-Ha;
memset(c,0,sizeof c);
add(m+1,1);
for (int i=n;i>=1;i--)
add(a[i],ans[i]=sum(a[i]+1));
if (sum(1)<k){
puts("-1");
return 0;
}
Ans.clear();
for (int i=0;k>0;Ans.push_back(i))
for (int j=i+1;j<=n;j++){
if (a[j]<=a[i])
continue;
if (k<=ans[j]){
i=j,k--;
break;
}
k-=ans[j];
}
printf("%d\n",(int)Ans.size());
for (int i=0;i<Ans.size()-1;i++)
printf("%d ",Ans[i]);
printf("%d",*--Ans.end());
return 0;
}
2018牛客网暑假ACM多校训练赛（第五场）H subseq 树状数组
原文：https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round5-H.html