題意：給n個(gè)數(shù)字表示一個(gè)長度為n的數(shù)組a，再給出一個(gè)長度為n的數(shù)組k，k[i] 表示數(shù)組a的a[k[i]] 在第i時(shí)刻后可用。輸出n個(gè)數(shù)瓜浸，表示第i個(gè)時(shí)刻的最長上升子序列的長度。a數(shù)組和k數(shù)組都是1~n的隨機(jī)排列寞秃，n<5e4
題解：復(fù)雜度分析題斟叼。首先需要知道一個(gè)隨機(jī)排列的期望LIS長度是 的（為什么是？
出題人說是就是了 參考 ）那么暴力地從后往前做這件事：如果碰到一個(gè)元素不可用而這個(gè)元素在這個(gè)時(shí)刻已經(jīng)不可用了春寿，那么就重新跑一遍LIS朗涩，這件事的概率 ， 從而總復(fù)雜度
順便還要記錄一下每個(gè)元素的前一個(gè)元素是什么绑改，從而得到整個(gè)LIS有哪些元素
#include <algorithm>
#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;
using pii = pair<int, int>;
const int maxn = 5e4 + 10;
int arr[maxn];
int k[maxn];
int x[maxn];
unsigned long ans[maxn];
int vis[maxn];
int n;
unordered_set<int> lis(int clk)
{
vector<int> dp;
dp.push_back(0);
for (int i = 1; i <= n; i++)
{
if (k[i] > clk)
continue;
auto it = lower_bound(dp.begin(), dp.end(), arr[i]);
if (it == dp.end())
{
vis[arr[i]] = dp.back();
dp.push_back(arr[i]);
}
else
{
*it = arr[i];
it--;
vis[arr[i]] = *it;
}
}
unordered_set<int> res;
for (int i = dp.back(); i; i = vis[i])
{
res.insert(i);
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
int _;
cin >> _;
while (_--)
{
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
for (int i = 1; i <= n; i++)
{
cin >> x[i];
k[x[i]] = i;
}
auto res = lis(n);
ans[n] = res.size();
for (int i = n; i > 1; i--)
{
int val = arr[x[i]];
if (res.count(val))
{
res = lis(i - 1);
}
ans[i - 1] = res.size();
}
for (int i = 1; i <= n; i++)
{
cout << ans[i] << " \n"[i == n];
}
}
}
