AC
```c
#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l,END##i=r;i<=END##i;++i)
#define dn(r,l,i) for(int i=r,END##i=l;i>=END##i;--i)
using namespace std;
typedef long long i64;
const int INF =2147483647;
const int MAXN=1e5+3;
int n,t,H[MAXN],F[MAXN];
int main(){
while(~scanf("%d",&H[++n])); --n;
t=0,memset(F,0,sizeof(F)),F[0]=INF;
up(1,n,i){
int l=0,r=t+1; while(r-l>1){
int m=l+(r-l)/2;
if(F[m]>=H[i]) l=m; else r=m;
}
int x=l+1; // dp[i]
if(x>t) t=x; F[x]=H[i];
}
printf("%d\n",t);
t=0,memset(F,0,sizeof(F)),F[0]=0;
up(1,n,i){
int l=0,r=t+1; while(r-l>1){
int m=l+(r-l)/2;
if(F[m]<H[i]) l=m; else r=m;
}
int x=l+1;
if(x>t) t=x; F[x]=H[i];
}
printf("%d\n",t);
return 0;
}
```
by timmyliao @ 2024-03-23 18:32:09
@[timmyliao](/user/1095093)
你这换了种方法吧^.^
by queenbee @ 2024-03-29 21:07:48
@[kmltz](/user/1064275)
```
lower_bound(f1+1,f1+1+len1,ar[i],greater< int >())-f1
```
换成
```
f1[upper_bound(f1+1,f1+1+len1,ar[i],greater< int >())-f1 ]=ar[i];
```
就AC了
```cpp
using namespace std;
#include<bits/stdc++.h>
#define ll long long
const int N=1e5+7;
int n;
int ar[N];
int f1[N];
int f2[N];
int main(){
while(cin>>ar[++n]){
}
n--;
// cout<<ar[1];
// for(int i=1;i<=n;i++){
// f1[i]=1;
// }
int len1=1;
f1[1]=ar[1];
for(int i=2;i<=n;i++){
if(f1[len1]>=ar[i]){
len1++;
f1[len1]=ar[i];
}else{
f1[upper_bound(f1+1,f1+1+len1,ar[i],greater< int >())-f1 ]=ar[i];
}
}
cout<<len1<<endl;
int len2=1;
f2[1]=ar[1];
for(int i=2;i<=n;i++){
if(f2[len2]<ar[i]){
len2++;
f2[len2]=ar[i];
}else{
f2[lower_bound(f2+1,f2+1+len2,ar[i])-f2]=ar[i];
}
}
cout<<len2;
}
```
by queenbee @ 2024-03-29 21:08:39
@[queenbee](/user/789564)
嗯嗯!
by timmyliao @ 2024-03-30 06:59:27
@[queenbee](/user/789564) 感谢
by kmltz @ 2024-03-30 09:00:35