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
|
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1001000;
int T;
int a[N];
int pos[N];
int c[N], st[N<<2];
void buildtree(int p, int l, int r){
st[p] = 0;
if(l == r){
return;
}
int mid = l+r >> 1;
buildtree(p<<1, l, mid);
buildtree(p<<1|1, mid+1, r);
}
int query(int k, int L, int R, int l, int r){
if(l > r || L > R) return 0;
if(L > r || R < l) return 0;
if(L >= l && R <= r) return st[k];
int mid = L+R >> 1;
return max(query(k*2, L, mid, l, r), query(k*2+1, mid+1, R, l, r) );
}
void update(int k, int l, int r, int p, int val){
if(l == r){
st[k] = val;
return;
}
int mid = l+r >> 1;
if(p <= mid)
update(k<<1, l, mid, p, val);
else
update(k<<1|1, mid+1, r, p, val);
st[k] = max(st[k<<1], st[k<<1|1]);
}
int main(){
scanf("%d", &T);
int n;
while(T--){
scanf("%d", &n);
for(int i = 1; i <= n; i++){
scanf("%d", &a[i]);
pos[a[i]] = i;
}
buildtree(1, 1, n);
for(int i = n; i >= 1; i--){
int p = pos[i];
if(p == 0) continue;
c[p] = query(1, 1, n, 1, p-1) + 1;
update(1, 1, n, p, c[p]);
}
int ans = *max_element(c+1, c+1+n);
printf("%d\n", ans);
for(int i = 1; i <= n; i++){
printf("%d%c", c[i], i==n?'\n':' ');
}
}
return 0;
}
|
