暴力LIS

反着做比较好写，把解冻看成冻住，每次看冻住的位置是不是当前LIS中的位置，如果不是就直接删除，如果是，就暴力重新计算一次LIS

#include 
    
     #define INF 0x3f3f3f3f#define full(a, b) memset(a, b, sizeof a)#define __fastIn ios::sync_with_stdio(false), cin.tie(0)#define pb push_backusing namespace std;using LL = long long;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}template 
     
      inline A __lcm(A a, A b){ return a / __gcd(a, b) * b; }template 
      
       inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 50005;int _, n, a[N], fr[N], dp[N], f[N], lis, ans[N];bool vis[N], pos[N];void calc(){    full(f, INF), full(dp, 0), lis = 0;    for(int i = 1; i <= n; i ++){        if(!vis[i]) continue;        int p = (int)(lower_bound(f + 1, f + n + 1, a[i]) - f);        if(f[p] == INF){            f[p] = a[i], dp[i] = p;            lis = max(lis, p);        }        else{            f[p] = a[i], dp[i] = p;        }    }    full(pos, false);    int len = lis;    for(int i = n; i >= 1; i --){        if(!vis[i]) continue;        if(!lis) break;        if(dp[i] == len){            pos[i] = true, len --;        }    }}int main(){    for(_ = read(); _; _ --){        n = read();        for(int i = 1; i <= n; i ++) a[i] = read();        for(int i = 1; i <= n; i ++) fr[i] = read();        full(vis, true), full(ans, 0);        calc();        for(int i = n; i >= 1; i --){            ans[i] = lis;            vis[fr[i]] = false;            if(pos[fr[i]]) calc();        }        for(int i = 1; i <= n; i ++)            printf("%d%c", ans[i], " \n"[i == n]);    }    return 0;}