提交时间:2022-07-19 11:51:12
运行 ID: 52254
#include<cstdio> #include<algorithm> #include<ctype.h> #include<cstring> #include<iostream> #include<vector> #include<queue> #include<ctime> #include<cmath> #include<queue> #include<map> #include<set> #include<unordered_map> #include<stack> #define pr pair<int,int> #define eps 1e-8 #define db double using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-')f=-1; ch=getchar(); } while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); } return x*f; } const int N=1000005; pr awa[N]; int n,b[N],tot; bool cmp(pr x,pr y) { return x.second-x.first>y.second-y.first; } int que(int x) { int l=1,r=tot; while(l<=r) { int mid=(l+r)>>1; if(b[mid]==x) return mid; if(b[mid]>x) r=mid-1; else l=mid+1; } return 0; } int dp[N],p[N]; bool cmpp(int x,int y) { return awa[x].first<awa[y].first; } int val[N<<2]; void modify(int L,int R,int pos,int k,int cur) { if(L==R) return val[cur]=max(val[cur],k),void(); int mid=(L+R)>>1; if(pos<=mid) modify(L,mid,pos,k,cur<<1); else modify(mid+1,R,pos,k,cur<<1|1); val[cur]=max(val[cur<<1],val[cur<<1|1]); } void del(int L,int R,int pos,int cur) { if(L==R) return val[cur]=0,void(); int mid=(L+R)>>1; if(pos<=mid) del(L,mid,pos,cur<<1); else del(mid+1,R,pos,cur<<1|1); val[cur]=max(val[cur<<1],val[cur<<1|1]); } int query(int L,int R,int l,int r,int cur) { if(l<=L&&R<=r) return val[cur]; int mid=(L+R)>>1; if(r<=mid) return query(L,mid,l,r,cur<<1); else if(l>mid) return query(mid+1,R,l,r,cur<<1|1); return max(query(L,mid,l,mid,cur<<1),query(mid+1,R,mid+1,r,cur<<1|1)); } void work(int l,int r) { if(l==r) return dp[p[l]]=max(1,dp[p[l]]),void(); int mid=(l+r)>>1; work(l,mid); sort(p+l,p+mid+1,cmpp); vector<int>ovo; for(int i=mid+1; i<=r; i++) ovo.push_back(p[i]); sort(p+mid+1,p+r+1,cmpp); int nl=l; for(int i=mid+1; i<=r; i++) { while(nl<=mid&&awa[p[nl]].first<=awa[p[i]].first) modify(1,tot,awa[p[nl]].second,dp[p[nl]],1),nl++; dp[p[i]]=max(dp[p[i]],query(1,tot,awa[p[i]].second,tot,1)+1); } for(int i=l; i<=mid; i++) del(1,tot,awa[p[i]].second,1); int cur=mid; for(auto v:ovo) p[++cur]=v; work(mid+1,r); } int main() { // freopen("awa.in","r",stdin); // freopen("awa.out","w",stdout); n=read(); for(int l,r,i=1; i<=n; i++) l=read(),r=read(),awa[i]=make_pair(l,r),b[++tot]=l,b[++tot]=r; sort(b+1,b+tot+1); tot=unique(b+1,b+tot+1)-(b+1); sort(awa+1,awa+n+1,cmp); for(int i=1; i<=n; i++) awa[i].first=que(awa[i].first),awa[i].second=que(awa[i].second),p[i]=i; work(1,n); int ans=0; for(int i=1; i<=n; i++) ans=max(ans,dp[i]); printf("%d\n",ans); // fclose(stdin); // fclose(stdout); return 0; }