HDU 6635 Nonsense Time【暴力LIS+记录路径】

HDU 6635 Nonsense Time【暴力LIS+记录路径】

题意：给你一个n的全排列，每次选一个元素到集合S，然后每次求出来集合S的LIS。

思路：反过来考虑，相当于每次删除一个元素，然后求LIS。由于保证数据随机，所以可以考虑暴力找，如果当前删这个元素不是LIS的路径，那么删除这个元素对答案无影响，否则就再暴力求LIS。另外学到了nlogn求路径，之前一直以为不可以求。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ls rt << 1
#define rs rt << 1 | 1
#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1|1
const int maxn = 5e4 + 10;
const int inf = 0x3f3f3f3f;
int a[maxn], b[maxn], pos[maxn], pre[maxn], p[maxn], ans[maxn];
bool vis[maxn];
int len;void LIS(int n)
{memset(b, 0x3f, (n + 1) * sizeof(int));memset(vis, false, (n + 1) * sizeof(bool));pos[0] = 0;for(int i = 1; i <= n; ++i){if(a[i] == -1) continue;int id = lower_bound(b + 1, b + n + 1, a[i]) - b;b[id] = a[