CF1097E Egor and an RPG game

Link
首先考虑求出\(f\)。
实际上达到\(f\)上界的序列是形如下列形式的：\(1,3,2,6,5,4,10,9,8,7,15,14,13,12,11\dots\)。
即若\(f(n)=k\)，则\(\frac{k(k+1)}2\le n\le\frac{(k+1)(k+2)}2\)。
我们将构造性地证明该结论。
如果该排列的LIS的长度\(\ge k\)，那么我们把它删掉，然后递归处理。
否则我们把该排列划分为\(\le k\)个下降子序列。

#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
namespace IO
{
    char ibuf[(1<<21)+1],obuf[(1<<21)+1],st[11],*iS,*iT,*oS=obuf,*oT=obuf+(1<<21);
    char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
    void Flush(){fwrite(obuf,1,oS-obuf,stdout),oS=obuf;}
    void Put(int x){*oS++=x;if(oS==oT)Flush();}
    int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}
    void write(int x,int c){int top=0;while(x)st[++top]=(x%10)+48,x/=10;while(top)Put(st[top--]);Put(c);}
}
using IO::read;
using IO::write;
using std::vector;
const int N=100007;
int f[N],g[N],h[N],las[N],in[N];
vector<vector<int>>ans,t;
void work(vector<int>a)
{
    int n=a.size(),c=0;
    t={{}},g[0]=-1;
    for(int i=0,l,r,mid;i<n;++i)
    {
    for(l=0,r=c;l<r;) a[i]<a[g[(mid=(l+r)>>1)+1]]? r=mid:l=mid+1;
    if(l==c) ++c,t.push_back({});
    g[h[i]=++l]=i,las[i]=g[l-1],t[l].push_back(a[i]);
    }
    if(c>f[n])
    {
    memset(in,0,n<<2),ans.push_back({});
    for(int i=g[c];~i;i=las[i]) in[i]=1;
    vector<int>r;
    for(int i=0;i<n;++i) in[i]? ans.back().push_back(a[i]):r.push_back(a[i]);
    work(r);
    }
    else
    {
    int x=ans.size()-1;ans.resize(ans.size()+c);
    for(int i=0;i<n;++i) ans[x+h[i]].push_back(a[i]);
    }
}
int main()
{
    for(int i=1;i<447;++i) f[i*(i+1)/2]=i;
    for(int i=1;i<=100000;++i) f[i]=f[i]?f[i]:f[i-1];
    for(int T=read(),n;T;--T)
    {
    vector<int>a(n=read());
    for(int i=0;i<n;++i) a[i]=read();
    ans.clear(),work(a),write((int)ans.size(),'\n');
    for(auto vec:ans)
    {
        write((int)vec.size(),' ');
        for(int x:vec) write(x,' ');
        IO::Put('\n');
    }
    }
    IO::Flush();
}

CF1097E Egor and an RPG game

原文：https://www.cnblogs.com/cjoierShiina-Mashiro/p/12288564.html