dp[i] 表示长度为 i 的序列最后一个数的最小值。 考虑转移时加入一段区间[l,r]。 对于最大的满足 dp[i]<l 的位置：
dp[i+1]=min(dp[i+1],l) 因为 dp[i+1]>=l ，所以转移可以变为直接赋值（一定发生）。 对于最大的满足 dp[j]<r 的位置： dp[k+1]=min(dp[k+1],dp[k]+1),k∈[i+1,j] 显然 dp 数组严格单调递增，即 dp[i+1]>=dp[i]+1 ，所以上述转移必定发生。 所以我们可以通过一颗非旋转 treap 维护 dp 数组，每次删去 dp[j+1] 这个节点，对于 dp[i+1]−dp[j] 这段 dp 区间整体 +1 并右移，再在原来的 dp[i+1] 前加入一个新的 dp[i+1]=l 的节点。这些操作都可以通过 split,merge 较为简单地实现。 #include <bits/stdc++.h> #define gc getchar() #define ll long long #define N 300009 #define inf 0x3f3f3f3f #define rd(x) (rand()%(x)) using namespace std; int n,l[N],r[N]; struct node { int size,val,key,add; node *lson,*rson; node(int v) { val=v; key=rd(100000); if (key<=0) key+=100000; lson=rson=NULL; size=1; add=0; } }; typedef node * pnode; int read() { int x=1; char ch; while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1; int s=ch-'0'; while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0'; return s*x; } void down(pnode now) { now->val+=now->add; if (now->lson) now->lson->add+=now->add; if (now->rson) now->rson->add+=now->add; now->add=0; } pnode merge(pnode L,pnode R) { if (!L) return R; if (!R) return L; if (L->key>R->key) { down(L); L->rson=merge(L->rson,R); return L; } else { down(R); R->lson=merge(L,R->lson); return R; } } void split(pnode now,int val,pnode &L,pnode &R) { if (!now) { L=R=NULL; return; } down(now); if (now->val>=val) { split(now->lson,val,L,now->lson); R=now; return; } else { split(now->rson,val,now->rson,R); L=now; return; } } int find_begin(pnode now) { down(now); if (!now->lson) return now->val; return find_begin(now->lson); } int get_Ans(pnode now) { if (!now) return 0; down(now); return get_Ans(now->lson)+get_Ans(now->rson)+(now->val<inf); } pnode root,L,M,R,rest; int main() { n=read(); for (int i=1;i<=n;i++) l[i]=read(),r[i]=read(); root=new node(0); for (int i=1;i<=n;i++) root=merge(root,new node(i+inf)); for (int i=1;i<=n;i++) { split(root,l[i],L,R); split(R,r[i],M,R); if (M) M->add++; int Min=find_begin(R); split(R,Min+1,rest,R); root=merge(L,new node(l[i])); root=merge(root,M); root=merge(root,R); } printf("%d\n",get_Ans(root)-1); return 0; }