hdu 6635 Nonsense Time 暴力求最长上升子序列LIS

hdu 6635 Nonsense Time 暴力求最长上升子序列LIS

题意：

       现在给你n个随机的成排序的数ai（注意是随机的！），现在他们都是隐藏的，然后再给你一个n的排序bi，每次你要依次把bi这个位置上的数依次显现，问你每次操作之后的最长上升序列数LIS是多少。

做法：

       考虑时间倒流，看作一个完整的排列按照一定顺序依次删除每个数，然后每次需要计算LIS 的长度。
       首先在 O(n log n) 的时间内求出 LIS，并找到一个 LIS。当删除 x 时，如果 x 不在之前找到的那个 LIS 中，那么显然 LIS 的长度是不会变化的，否则暴力重新计算出新的 LIS 即可。因为数据随机，因此 LIS 的期望长度是 O(√n)，删除的 x 位于 LIS 中的概率是 √1n，也就是说期望删除 O(√n) 个数才会修改 LIS，那么 LIS 变化的次数不会很多。期望时间复杂度为 O(n√n log n)。

#include<bits/stdc++.h>
#define ll long long 
#define max 50005
using namespace std;int a[max],b[max],vis[max];
int d[max],path[max],ans[max];
int us[max]; 
int n;
int solve(){int len=0;fill(d,d+max,0); for(int i=0;i<n;i++){if(vis[i] == -1) continue;int it = lower_bound(d,d+len,a[i]) - d;if(it==l