HDU-6635

Posted on | In | Views:

题意

给两个排列 $a , b$ ，$a$ 一开始全都封闭，从左到右遍历 $b$ ，每次释放一个 $\Large a_{b_i}$ ，问每个时刻，释放后的序列 $a$ 的 $LIS$

题解

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <bits/stdc++.h>
using namespace std;
#define forl(i, l, r) for (int i = l; i <= r; i++)
#define forr(i, r, l) for (int i = r; i >= l; i--)
#define for1(i, n) for (int i = 1; i <= n; i++)
#define fro1(i, n) for (int i = 1; i <= n; i++)
#define for0(i, n) for (int i = 0; i < n; i++)
#define fro0(i, n) for (int i = 0; i < n; i++)
#define meminf(a) memset(a, inf, sizeof(a))
#define mem_1(a) memset(a, -1, sizeof(a))
#define mem0(a) memset(a, 0, sizeof(a))
#define memcp(a,b) memcpy(a,b,sizeof(b))
#define oper(type) bool operator <(const type y)const
#define mp make_pair
#define pu_b push_back
#define pu_f push_front
#define po_b pop_back
#define po_f pop_front
#define fi first
#define se second
#define whiel while
#define retrun return
typedef pair<long long, long long> pll;
typedef vector<long long> vll;
typedef pair<int, int> pii;
typedef unsigned long long ull;
typedef vector<int> vii;
typedef double db;
typedef long long ll;
typedef int itn;
int in(int &a,int &b,int &c,int &d){return scanf("%d%d%d%d",&a,&b,&c,&d);}
int in(int &a,int &b,int &c){return scanf("%d%d%d",&a,&b,&c);}
int in(int &a,int &b){return scanf("%d%d",&a,&b);}
int in(ll &a){return scanf("%lld",&a);}
int in(int &a){return scanf("%d",&a);}
int in(char *s){return scanf("%s",s);}
int in(char &s){return scanf("%c",&s);}
int in(db &a){return scanf("%lf",&a);}
void out(int a){printf("%d ",a);}
void outln(int a){printf("%d\n",a);}
void out(ll a){printf("%lld ",a);}
void outln(ll a){printf("%lld\n",a);}
const db pi = acos((db)-1);
const ll inf =0x3f3f3f3f;
const db eps = 1e-8;
const int N = 5.1e4;
const int M = 2.1e5;
const ll mod = 1e9+7;
int sign(db a) { return a < -eps ? -1 : a > eps;}
int db_cmp(db a, db b){ return sign(a-b); }

int a[N],pre[N],b[N],ans[N],cnt,n,pp[N],pr[N];
bool vis[N],cho[N];
void redo(){
    cnt=0;
    mem0(cho);
    int last=0;
    for1(i,n){
        if(!vis[i]){
            int posi=upper_bound(pre+1,pre+1+cnt,a[i])-pre;
            // printf("sa%d %d\n",i,a[i]);
            if(posi==cnt+1){
                pre[++cnt]=a[i];
                pr[cnt]=i;
                pp[i]=pr[cnt-1];
                last=i;
                // printf("sa%d\n",i);
                // sta[cnt].push(i);
            }else { 
                pre[posi]=a[i];
                pr[posi]=i;
                pp[i]=pr[posi-1];
                // no[i]=posi;
                // sta[posi].push(i);
            }
        }
    }
    while(last){
        cho[last]=1;
        // out(last);
        last=pp[last];
    }
    // puts("");
}
void del(int x){
    vis[x]=1;
    if(cho[x])redo();
}
int main() {
#ifdef PerpEternal
    freopen("/Users/perpeternal/Documents/Sketch/data/in.dat", "r", stdin);
    freopen("/Users/perpeternal/Documents/Sketch/data/out.dat", "w", stdout);
#endif
    //ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t;
    in(t);
    whiel(t--){
        in(n);
        mem0(vis);
        for1(i,n)in(a[i]);
        for1(i,n)in(b[i]);
        redo();
        for(int i=n;i>0;i--){
            ans[i]=cnt;
            del(b[i]);
        }
        for1(i,n){
            if(i==n)outln(ans[i]);
            else out(ans[i]);
        }
    }
    return 0;
}