2019HDU多校第六场 HDU6635 Nonsense Time

2019HDU多校第六场 HDU6635 Nonsense Time

题意：给你一个n的排列p，再给你一个n的排列k，一开始所有p不可用，对于每个k_i表示下标为k₁~k_i的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;
}

转载于:.html