题目描述：
题解：
平衡树模拟dp？
设$dp[i]$表示当前状态下长为$i$的合法子序列最后一位的最小值。
容易发现$dp[i]<dp[i+1]$。
然后就可以$dp$了。
（当前可操作区间为$[l,r]$）
1.$dp[i-1]<l$，有$dp[i]=min(dp[i],l)$。
此时满足$dp[i-1]<l \le dp[i]$。
2.$l \le dp[i-1] < r$，有$dp[i]=min(dp[i],dp[i-1]+1)$，
其实右边一定最右，因为$dp[i-1]<dp[i]$。
3.$dp[i-1] \ge r$，此时$dp[i]=dp[i]$。
我们可以用平衡树维护这个转移。
对于转移1，我们要插入一个$l$。
对于转移2，我们要将一段区间平移后+1。
所以，用splay维护插入、区间加法和删除。
注意三者顺序。
（splay双旋写成反双旋卡在第80个点卡了半天
代码：
#include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; const int inf = 0x7f7f7f7f; const int N = 500050; template<typename T> inline void read(T&x) { T f = 1,c = 0;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} x = f*c; } int n; struct Splay { int tot,rt,ch[N][2],fa[N],siz[N]; int w[N],tag[N]; Splay() { tot = 2;rt = 1; w[1] = -inf,w[2] = inf; fa[2] = 1,ch[1][1] = 2; siz[1] = 2,siz[2] = 1; } void update(int u){siz[u]=siz[ch[u][0]]+siz[ch[u][1]]+1;} void add(int u,int k){ if(u)w[u]+=k,tag[u]+=k;} void pushdown(int u) { if(tag[u]) { add(ch[u][0],tag[u]); add(ch[u][1],tag[u]); tag[u]=0; } } int now; void rotate(int x) { int y = fa[x],z = fa[y],k = (ch[y][1]==x); ch[z][ch[z][1]==y]=x,fa[x]=z; ch[y][k]=ch[x][!k],fa[ch[x][!k]]=y; ch[x][!k]=y,fa[y]=x; update(y),update(x); } int sta[N],tl; void down(int x) { sta[tl=1]=x; while(fa[x])x=fa[x],sta[++tl]=x; while(tl)pushdown(sta[tl--]); } void splay(int x,int goal) { down(x); while(fa[x]!=goal) { int y = fa[x],z = fa[y]; if(z!=goal) (ch[y][1]==x)^(ch[z][1]==y)?rotate(x):rotate(y); rotate(x); } if(!goal)rt=x; } void get_qq(int u,int k) { if(!u)return ;pushdown(u); if(w[u]<=k)now=u,get_qq(ch[u][1],k); else get_qq(ch[u][0],k); } void get_hj(int u,int k) { if(!u)return ;pushdown(u); if(w[u]>=k)now=u,get_hj(ch[u][0],k); else get_hj(ch[u][1],k); } int qq(int k){get_qq(rt,k);splay(now,0);return now;} int hj(int k){get_hj(rt,k);splay(now,0);return now;} void work(int l,int r) { int lp,rp,u; lp = hj(r); if(lp!=2) { rp = hj(w[lp]+1),lp = qq(w[lp]-1); splay(lp,0),splay(rp,lp); ch[rp][0]=0; update(rp),update(lp); } // u = qq(inf-1); // splay(u,0); lp = qq(l-1),rp = hj(r); splay(lp,0),splay(rp,lp); add(ch[rp][0],1); // u = qq(inf-1); // splay(u,0); rp = hj(w[lp]+1); splay(lp,0),splay(rp,lp); u = ++tot;w[u]=l; siz[u] = 1,fa[u] = rp,ch[rp][0] = u; update(rp),update(lp); // splay(u,0); // int mid = (2int*l+3int*r)/5; u = qq(inf-1); splay(u,0); } }tr; int main() { // freopen("tt.in","r",stdin); read(n); for(int l,r,i=1;i<=n;i++) { read(l),read(r); tr.work(l,r); } printf("%d\n",tr.siz[tr.rt]-2); return 0; }