构造形如$1,3,2,6,5,4,10,9,8,7,...$的序列，不难发现其中前$\frac{k(k+1)}{2}$项最少要划分为$k$个单调子序列

由此，取$k=f(n)+1$时应有$\frac{k(k+1)}{2}>n$，也即有$f(n)\ge \max_{\frac{k(k+1)}{2}\le n}k$

令$g(n)$为后者，那么只需要保证划分为不超过$g(n)$个单调子序列即可

考虑其最长上升子序列，假设长度为$x$，对其分类讨论：

1.若$x\ge g(n)+1$，则有$g(n-x)+1\le g(n)$，那么直接选择该序列即可

关于这个式子，即求证$\frac{g(n)(g(n)+1)}{2}>n-(g(n)+1)$，化简后也即$\frac{(g(n)+1)(g(n)+2)}{2}>n$，那么如果其不满足即与$g(n)$的最大性矛盾

2.若$x\le g(n)$，注意到原序列可以被划分为$x$个下降子序列，直接划分为下降子序列即可

直接暴力即可，注意到$g(n)$是$o(\sqrt{n})$级别的，复杂度为$o(n\sqrt{n}\log n)$

对于这个复杂度，如果$\log$是线段树复杂度可能无法通过，需要使用经典的dp+二分求LIS，下面来分别考虑两种序列如何划分——

对于最长上升子序列，记录每一个数字插入时上一个位置的数字，往前找即可

对于下降子序列，注意到每一个位置上的数都单调递增，即分别构成一个下降子序列

总复杂度为$o(n\sqrt{n}\log n)$，且常数较小，可以通过

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 100005
 4 #define ll long long
 5 vector<int>ans[N];
 6 int t,n,m,tot,a[N],val[N],Pos[N],pre[N],fi[N],nex[N],vis[N];
 7 int main(){
 8     scanf("%d",&t);
 9     while (t--){
10         scanf("%d",&n);
11         for(int i=1;i<=n;i++)scanf("%d",&a[i]);
12         m=0;
13         while (n){
14             tot=0;
15             for(int i=1;i<=n;i++){
16                 int pos;
17                 if ((!tot)||(val[tot]<a[i])){
18                     pos=++tot;
19                     fi[pos]=i;
20                 }
21                 else{
22                     pos=lower_bound(val+1,val+tot+1,a[i])-val;
23                     nex[Pos[pos]]=i;
24                 }
25                 val[pos]=a[i],Pos[pos]=i;
26                 if (pos==1)pre[i]=0;
27                 else pre[i]=Pos[pos-1];
28             }
29             if ((ll)tot*(tot+1)/2<=n){
30                 for(int i=1;i<=tot;i++){
31                     ans[++m].clear();
32                     for(int j=fi[i];j!=Pos[i];j=nex[j])ans[m].push_back(a[j]);
33                     ans[m].push_back(a[Pos[i]]);
34                 }
35                 break;
36             }
37             ans[++m].clear();
38             for(int i=1;i<=n;i++)vis[i]=0;
39             for(int i=Pos[tot];i;i=pre[i])vis[i]=1;
40             int nn=0;
41             for(int i=1;i<=n;i++){
42                 if (!vis[i])a[++nn]=a[i];
43                 else ans[m].push_back(a[i]);
44             }
45             n=nn;
46         }
47         printf("%d\n",m);
48         for(int i=1;i<=m;i++){
49             printf("%d",ans[i].size());
50             for(int j=0;j<ans[i].size();j++)printf(" %d",ans[i][j]);
51             printf("\n");
52         }
53     }
54     return 0;
55 } 

View Code