BZOJ5484（LIS性质+树状数组）
【Usaco2018 Dec】Sort It Out
（冗长的）题面描述：
FJ有N（1≤N≤10^5）头奶牛（分别用1…N编号）排成一行。FJ喜欢他的奶牛以升序排列，不幸的是现在她们的顺序被打乱了。在过去FJ曾经使用一些诸如“冒泡排序”的开创性的算法来使他的奶牛排好序，但今天他想偷个懒。
取而代之，他会每次对着一头奶牛叫道“按顺序排好”。当一头奶牛被叫到的时候，她会确保自己在队伍中的顺序是正确的（从她的角度看来）。只要有一头紧接在她右边的奶牛的编号比她小，她们就交换位置。然后，只要有一头紧接在她左边的奶牛的编号比她大，她们就交换位置。这样这头奶牛就完成了“按顺序排好”，在这头奶牛看来左边的奶牛编号比她小，右边的奶牛编号比她大。
FJ想要选出这些奶牛的一个子集，然后遍历这个子集，依次对着每一头奶牛发号施令（按编号递增的顺序），重复这样直到所有N头奶牛排好顺序。例如，如果她选出了编号为{2,4,5}的奶牛的子集，那么他会喊叫奶牛2，然后是奶牛4，然后是奶牛5。如果N头奶牛此时仍未排好顺序他会再次对着这几头奶牛喊叫，如果有必要的话继续重复。
由于FJ不确定哪些奶牛比较专心，他想要使得这个子集最小。此外，他认为K是个幸运数字。请帮他求出满足重复喊叫可以使得所有奶牛排好顺序的最小子集之中字典序第K小的子集。我们称{1,…,N}的一个子集S在字典序下小于子集T，当S的所有元素组成的序列（按升序排列）在字典序下小于T的所有元素组成的序列（按升序排列）。例如，{1,3,6} 在字典序下小于{1,4,5}。
Input
输入的第一行包含一个整数N。
第二行包含一个整数K（1≤K≤10^18）。第三行包含N个空格分隔的整数，表示从左到右奶牛的编号。
保证存在至少K个符合要求的子集。
Output
第一行输出最小子集的大小。
接下来输出字典序第K小的最小子集中奶牛的编号，每行一个数，升序排列。
Sample Input
4 1 4 2 1 3
Sample Output
2 1 4
HINT
//开始的时候序列为4213 。在FJ喊叫编号为1的奶牛之后，序列变为1423。 在FJ喊叫编号为4的奶牛之后，序列变为1234。在这个时候，序列已经完成了排序。
题解部分（作者也是上网学的嘤嘤嘤）
结论：
1.直观感受一下会发现找到LIS，LIS里的东西相对位置是不会变的，其他的移一移总会排序成功的，所以其他的就是最小集合了，第一问的答案就是n-LIS；
2.寻找字典序第k小的集合，相当于是寻找字典序第k大的LIS，然后把这个LIS删去，就是第二问的答案集合。
前置技能：
稍微懂点树状数组，及树状数组求LIS。
解决方法（我建议先看代码）：
1.树状数组bit[i]求LIS的同时再维护一下“以比i大的数字为开头、这个LIS长度下的序列的数量”。数量超过maxk的时候min一下砍掉（是一种常见手法），因为多了也没有用它只会询问maxk以内的，否则有可能爆longlong。
2.用vector存下每个长度的LIS是以哪些位置为起点，然后按长度从大到小枚举，看看第k个是哪个LIS，标记这些数字。因为之前维护了数量，所以这时就不用从1开始一个一个枚举到k了，一下砍下去一段。
代码：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>
#include <climits>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <sstream>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <fstream>
#include <bitset>
#define init(a, b) memset(a, b, sizeof(a))
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define irep(i, a, b) for (int i = a; i >= b; i--)
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
const int inf = 0x3f3f3f3f;
const ll INF = 1e18;
template <typename T> void read(T &x) {
x = 0;
int s = 1, c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-') s = -1;
for (; isdigit(c); c = getchar())
x = x * 10 + c - 48;
x *= s;
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
write(x);
puts("");
}/*-----正片开始-----*/const int maxn = 1e5 + 5;
const ll maxk = 1e18;
int n, a[maxn];
ll k;
struct Arr {
int len;
ll cnt;
Arr() {
len = 0, cnt = 0;
}
Arr(int a, ll b) {
len = a, cnt = b;
}
}dp[maxn], bit[maxn];
vector<int> v[maxn];
bool mark[maxn];
void Modify(Arr &a, Arr b) {
if (a.len > b.len) return;
if (a.len < b.len) {
a = b;
return;
}
a.cnt = min(maxk, a.cnt + b.cnt);
}
void Update(int x, Arr val) {
for (; x; x -= x&-x)
Modify(bit[x], val);
}
Arr Query(int x) {
Arr ret(0, 1);
for (; x <= n; x += x&-x)
Modify(ret, bit[x]);
return ret;
}
int main() {
read(n), read(k);
rep(i, 1, n) read(a[i]);
//树状数组维护一个后缀最大序列（的长度和此长度下的LIS个数），规则是：1.长度最大；2.如果长度相同，累加数量
irep(i, n, 1) {//比较字典序是从左往右，所以将此长度下的cnt集中在左端，故而倒序
dp[i] = Query(a[i] + 1);
v[++dp[i].len].push_back(i);
Update(a[i], dp[i]);
}
int LIS = Query(1).len;
for (int i = LIS, pos = 1; i; --i) {
for (int j = v[i].size() - 1; ~j; --j) {
//找字典序大的，所以倒着找。vector的插入导致其中的a[p]必然升序
int p = v[i][j];
if (dp[p].cnt < k) {//以当前数字为开头的所有LIS的数量都无法满足k的需求，则这个开头被pass
k -= dp[p].cnt;
} else {//说明要找的LIS以当前这个数字为开头
mark[a[p]] = true;
while (pos < p) dp[pos++].cnt = 0;
//选定这个数以后，因为是找LIS，所以它之前的数不能再选中
break;
}
}
}
writeln(n - LIS);
rep(i, 1, n) {
if (!mark[i])
writeln(i);
}
return 0;
}腾讯云开发者
