题意：给你一个n的排列p，再给你一个n的排列k，一开始所有p不可用，对于每个ki表示下标为k1~ki的p可用，求当前可用的所有p的最长上升子序列（可能表达的不是很清楚，这里看题面）
题解：题意等价于一个完整的排列按照一定顺序依次删除每个数，然后计算每次操作后的 LIS 长度。这样就好办了，首先在 O(nlogn) 的时间内求出 LIS，并记录一个 LIS(不会记录路径看这里)，当删除 x 时，如果 x 不在之前找 到的那个 LIS 中，那么显然 LIS 的长度是不会变化的，否则暴力重新计算出新的 LIS 即可。
#include <bits/stdc++.h> using namespace std; const int maxn = 50005, INF = 0x3f3f3f3f; int low[maxn], a[maxn], pos[maxn], k[maxn], ans[maxn]; bool in[maxn],vis[maxn]; int n, len; void LIS() { memset(low, INF, sizeof(low)); memset(in,false,sizeof(in)); int cnt=1; while(vis[cnt]==true) { cnt++; } low[1] = a[cnt]; len = 1; pos[cnt] = len; for (int i = 2; i <= n; i++) { if(vis[i]==true)continue; if (a[i] > low[len]) { low[++len] = a[i]; pos[i] = len; } else { int index = lower_bound(low + 1, low + 1 + len, a[i]) - low; low[index] = a[i]; pos[i] = index; } } //利用pos数组找到一个LIS,用in标记 int maxx = INF,tem=len; for (int i = n; i >= 1; i--) { if (tem == 0) break; if (pos[i] == tem && maxx >= a[i]) { in[i] = true; tem--; maxx = a[i]; } } } int main() { int t; scanf("%d", &t); while (t--) { memset(pos,0,sizeof(pos)); memset(vis,false,sizeof(vis)); scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); } LIS(); for (int i = 1; i <= n; i++) { scanf("%d", &k[i]); } ans[n]=len; for (int i = n; i >= 2; i--) { vis[k[i]] = true; pos[k[i]] = 0; if (in[k[i]] == false)//如果不在现在的LIS上 { ans[i-1] = len; } else { LIS(); ans[i-1] = len; } } for(int i=1;i<=n;i++) { printf("%d%s",ans[i],i==n?"\n":" "); } } return 0; }
2019HDU多校第六场 HDU6635 Nonsense Time
原文：https://www.cnblogs.com/Zeronera/p/11317508.html