有一定义域为R的连续函数f(x)，f(x)在(-∞,A)上严格单调递增，在 (A,+∞)上严格单调递减，其中 A 对于任意a<b≤A，均有f(a)<f(b)≤f(A) 对于任意a>b≥A，均有f(a)>f(b)≥f(A) 已知n个整点(xi,yi)（xi,yi是整数，xi互不相同），求f(x)最多有可能经过的点数。
输入
输入第一行一个整数n，表示点数。 接下来n行，每行两个整数xi,yi，表示一个点。
输出
输出一行一个整数，表示f(x)最多有可能经过的点数。
样例输入 Copy
【样例1】
3
3 5
4 4
5 1
【样例2】
2
1 2
2 2
样例输出 Copy
【样例1】
3
【样例2】
1
提示
对于100%的数据： ·1≤n≤105 ·xi互不相同，1≤xi,yi≤m≤105(m是一个描述xi,yi范围的参数）
题目大意：
中文题意
题目思路：
考虑经典套路，首先按照x排序
从1开始的最长上升子序列，从n开始的最长上升子序列
然而此时枚举最高点可能不对。
注意细节问题:A是一个整数 并没有要求 A是给出的点的整数
所以说样例:
2
1 2
3 2
的答案是2
所以当A不存在这里面时，那么就只要求 0~A递增 ，A~n递减。
此时就会出现三个细节问题：(由于考虑这个不全面wa到极致，wa到上头)
Note：q数组存储的题目给出的信息
1.如果q[i].x - q[i-1].x >1
此时只需要在左边找一个最长的上升子序列(从1开始)，从右边找一个最长上升子序列(从n开始)即可。因为此时你永远可以从中间选择一个点使得两边都成立
2.如果q[i].x - q[i-1].x == 1
并且此时q[i].y ！= q[i-1].y
那么和第一种情况相同
①如果答案时q[i].y 和 q[i-1].y的结尾序列，那么由于他们不相同，总有一个值可以成为峰值。
②否则和第一种情况相同
并且此时q[i].y == q[i-1].y(例如样例2):
那么当前就只能与prea[i-2]之前的最长上升子序列的长度匹配，原理也同第一种情况
这题数据真的好，少一种情况也不行
Code:
/*** keep hungry and calm CoolGuang!***/
#pragma GCC optimize(2)
#include <bits/stdc++.h>
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<string.h>
#include<iostream>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define ls k<<1
#define rs k<<1|1
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pp;
const ll INF=1e17;
const int maxn=1e6+6;
const int mod=998244353;
const double eps=1e-3;
inline bool read(ll &num)
{char in;bool IsN=false;
in=getchar();if(in==EOF) return false;while(in!='-'&&(in<'0'||in>'9')) in=getchar();if(in=='-'){ IsN=true;num=0;}else num=in-'0';while(in=getchar(),in>='0'&&in<='9'){num*=10,num+=in-'0';}if(IsN) num=-num;return true;}
ll n,m,p;
struct Line{
int x,y,f;
bool friend operator<(Line a,Line b){
return a.x < b.x;
}
}q[maxn];
ll prea[maxn],cura[maxn];
ll st[maxn];
int main(){
read(n);
for(int i=1;i<=n;i++) scanf("%d%d",&q[i].x,&q[i].y);
sort(q+1,q+1+n);
int s = 0;
for(int i=1;i<=n;i++){
if(!s||q[i].y>st[s]) st[++s] = q[i].y;
else{
int pos = lower_bound(st+1,st+1+s,q[i].y)-st;
st[pos] = q[i].y;
}
prea[i] = s;
}
s = 0;
for(int i=n;i>=1;i--){
if(!s||q[i].y>st[s]){
st[++s] = q[i].y;
}
else{
int pos = lower_bound(st+1,st+1+s,q[i].y)-st;
st[pos] = q[i].y;
}
cura[i] = s;
}
ll maxl = 0,ans = 0;
q[0].x = -1;
q[n+1].x = 1e7+7;
for(int i=1;i<=n+1;i++){
if(q[i].x-q[i-1].x>1) ans = max(prea[i-1]+cura[i],ans);
else{
if(q[i-1].y != q[i].y) ans = max(ans,prea[i-1]+cura[i]);
else ans = max(ans,prea[i-2]+cura[i]);
}
}
printf("%lld\n",ans);
return 0;
}
