C++14(g++5.4) 解法, 执行用时: 869ms, 内存消耗: 57312K, 提交时间: 2020-01-18 11:44:17

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N],d[N],f[N],vis[N],res,st[N],cnt[N]; vector<int> v,g[N];
inline void add(int x,int v){for(;x<=m;x+=(x&(-x))) d[x]=max(d[x],v);}
inline int ask(int x){int s=0; for(;x;x-=x&(-x)) s=max(s,d[x]); return s;}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)   scanf("%d",&a[i]),v.push_back(a[i]);
    sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
    m=v.size();
    for(int i=1;i<=n;i++) a[i]=lower_bound(v.begin(),v.end(),a[i])-v.begin()+1;
    for(int i=1;i<=n;i++){
        f[i]=ask(a[i])+1;   add(a[i],f[i]);     res=max(res,f[i]);
    }
    vis[res+1]=1e9;
    for(int i=n;i>=1;i--)   if(vis[f[i]+1]>=a[i]){
        vis[f[i]]=max(a[i],vis[f[i]]);  st[i]=1;
    }
    for(int i=1;i<=n;i++)   if(st[i])   cnt[f[i]]++;
    for(int i=1;i<=n;i++)   printf("%d ",res-(st[i]&&cnt[f[i]]==1));
    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 391ms, 内存消耗: 26236K, 提交时间: 2023-04-12 20:06:14

#include <bits/stdc++.h>
#define LL long long
#define GG int
#define For(i, j, k) for(int i=j; i<=k; i++)
#define Dow(i, j, k) for(int i=j; i>=k; i--)
using namespace std;

const int N=1e6+11;
int n, mx, h[N], f[N], tmp[N], v[N], wzt[N];
	
int main() {
	scanf("%d", &n);  
	For(i, 1, n) scanf("%d", &h[i]); 
	For(i, 1, n) tmp[i] = 2e9; 
	For(i, 1, n) {
		int pos = upper_bound(tmp+1, tmp+n+1, h[i])-tmp;
		f[i] = pos;
		mx = max(mx, pos); 
		tmp[pos] = min(h[i], tmp[pos]);
	}
	For(i, 0, n+2) tmp[i] = 0;
	Dow(i, n, 1) 
		if(f[i]==mx || tmp[f[i]+1]>=h[i]) {
			v[i] = 1;
			++wzt[f[i]];
			tmp[f[i]] = max(tmp[f[i]], h[i]);
		}
	For(i, 1, n) 
		if(v[i]==wzt[f[i]]) 
			printf("%d ", mx-1); 
		else 
			printf("%d ", mx); 
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 461ms, 内存消耗: 29276K, 提交时间: 2023-05-23 09:48:59

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int n,x,m,mm,g[1000005],a[1000005],f[1000005],h[1000005],cnt[1000005],p[1000005];
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	for (int i=1;i<=n;++i)
	{
		x=upper_bound(h+1,h+m+1,a[i])-h;
		h[x]=a[i];
		if (x>m)	m=x;
		f[i]=x;
	}
	for (int i=n;i;--i)
	{
		x=upper_bound(g+1,g+mm+1,a[i],greater<int>())-g;
		g[x]=a[i];
		if (x>mm)	mm=x;
		p[i]=x;
	}
	for (int i=1;i<=n;++i)
		if (f[i]+p[i]==m+1)
			cnt[f[i]]++;
	for (int i=1;i<=n;++i)
	{
		if (cnt[f[i]]==1 && f[i]+p[i]==m+1)	x=m-1;
		else x=m;
		printf("%d%c",x,(i==n)?'\n':' ');
	}
	return 0;
}