https://vijos.org/p/1369
求出现第K个数的（位置不变）LIS
思路：
把左边大于等于K的去掉，右边小于等于K的去掉
然后直接做LIS即可
注意n=300000，不能O(n^2)必须O(nlog n)
[code lang="cpp"]
#include<cstdio>
#include<iostream>
#define MAXN 333333
#define INF 2147483647
using namespace std;
int dp[MAXN], a[MAXN], s[MAXN], g[MAXN];
int n, k, len = 2;
int cnt = 1, ans = -1;
int findx(int w){
int l = 0, r = len;
while(r - l > 1){
int mid = (l + r) >> 1;
if (g[mid] < w){
l = mid;
}else{
r = mid;
}
}
return l;
}

int main(){
scanf("%d%d", &n, &k);
k--;
for (int i = 0; i < n; i++) scanf("%d", &a[i]), g[i] = INF;
for (int i = 0; i < k; i++){
if (a[i] < a[k]){
s[cnt++] = a[i];
}
}
s[cnt++] = a[k];
g[1] = s[1];
dp[1] = 1;
for (int i = k + 1; i < n; i++) if (a[i] > a[k]) s[cnt++] = a[i];
cnt--;
ans = dp[1];
for (int i = 2; i <= cnt; i++){
int r = findx(s[i]);
dp[i] = r + 1;
if (g[dp[i]] == INF) len++;
g[dp[i]] = min(g[dp[i]], s[i]);
ans = max(dp[i], ans);
}
cout << ans << endl;
}[/code]