C++14(g++5.4) 解法, 执行用时: 23ms, 内存消耗: 2272K, 提交时间: 2019-12-21 21:33:09

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+10;
#define fi first
#define se second
#define pb push_back
int n,a[N];
int t[N];
int add(int now){
    int b=0;
    for(;now<N;now+=now&-now)b=max(t[now],b);
    return b;
}
int get(int x,int b){
    for(;x;x-=x&-x)t[x]=max(b,t[x]);
}
int f[N];
int main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int G=0;
    for(int i=n;i>=1;i--){
        f[i]=add(a[i]+1)+1;
        get(a[i],f[i]);
        G=max(G,f[i]);
    }
    cout<<G<<endl;
    for(int i=1;i<=n;i++){
        if(f[i]==G)cout<<i<<' ',G--;
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 21ms, 内存消耗: 2148K, 提交时间: 2020-02-29 17:22:39

#include<bits/stdc++.h>
using namespace std;

int t=0,V[100005],S[100005],a[100005];
int main()
{
    int i,j,n,l,r,m;
	scanf("%d",&n);
	for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(S[0]=1e9,i=n;i;i--)
	{
		if(a[i]<S[t])S[++t]=a[i],V[i]=t;
		else 
		{
			for(l=1,r=t;l<=r;)
			{
				m=(l+r)>>1;
				if(S[m]<=a[i])j=m,r=m-1;
				else l=m+1;
			}
			V[i]=j,S[j]=a[i];
		}
	}
	printf("%d\n",t);
    for(i=1;i<=n;i++)if(V[i]==t)printf("%d ",i),t--;
    return 0;
}