题目：http://codeforces.com/contest/809/problem/D
如果值是固定的，新加入一个值，可以让第一个值大于它的那个长度的值等于它。
如今值是一段区间，就对区间内的dp值都有影响；中间的那些的值变成了上一个的值+1，左边 l 处多了一个点，右边第一个大于等于 r 的点被删掉。
用 splay 维护这些点；点的个数就是最多能达到的长度。
又好好学习了一番 splay 。带有标记的原来是要在那个 splay 操作前那样一条链地 pushdown下来呀。
非常奇怪的是按题解写法，找第一个小于边界的值，再找右边界那个值的 nxt ，就没问题；而自己找第一个大于等于的值，就会TLE。那个T的点是所有 l , r 都是 1,1e9 的，也许和这个有关？
加“哨兵”十分方便。
别忘了 insert 也要 splay 。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3e5+;
int n,c[N][],tg[N],val[N],fa[N],ans,rt,tot;
inline int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='') ret=(ret<<)+(ret<<)+ch-'',ch=getchar();
return fx?ret:-ret;
}
inline void rotate(int x,int &k)
{
int y=fa[x],z=fa[y];
if(y==k) k=x;
else c[z][y==c[z][]]=x;
int d=(x==c[y][]);
fa[x]=z; fa[c[x][!d]]=y; fa[y]=x;
c[y][d]=c[x][!d]; c[x][!d]=y;
}
inline void down(int cr)
{
if(!tg[cr])return;
int ls=c[cr][],rs=c[cr][];
if(ls) tg[ls]+=tg[cr],val[ls]+=tg[cr];
if(rs) tg[rs]+=tg[cr],val[rs]+=tg[cr];
tg[cr]=;
}
inline void push(int cr)
{
if(fa[cr]) push(fa[cr]);
down(cr);
}
inline void splay(int x,int &k)
{
push(x);
while(x!=k)
{
int y=fa[x],z=fa[y];
if(y!=k)
{
if((x==c[y][])^(y==c[z][]))
rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
inline int lower(int x)
{
int cr=rt,ret=;
while(cr)
{
down(cr);
if(val[cr]<x)
ret=cr,cr=c[cr][];
else cr=c[cr][]; // if(val[cr]>=x)
// ret=cr,cr=c[cr][0];
// else cr=c[cr][1];
}
return ret;
}
inline void del(int cr)
{
splay(cr,rt);
int pr=c[cr][],nt=c[cr][];
while(c[pr][])pr=c[pr][];
while(c[nt][])nt=c[nt][];
splay(pr,rt); splay(nt,c[rt][]);
fa[cr]=; c[nt][]=;
}
inline void insert(int &cr,int p,int pr)//&
{
if(!cr){fa[cr=++tot]=pr;val[cr]=p;splay(cr,rt);return;}//
down(cr);
insert(c[cr][val[cr]<p],p,cr);
}
int nxt(int x)
{
splay(x,rt);//
int cr=c[x][];
while(c[cr][])cr=c[cr][];
return cr;
}
inline void solve(int l,int r)
{
int x=lower(l),y=lower(r),t=nxt(y);
if(x!=y)
{
splay(x,rt); splay(t,c[rt][]);
// val[x]++;
tg[c[t][]]++; val[c[t][]]++;
} if(t!=) del(t),ans--;
// if(y!=2) del(y),ans--;
insert(rt,l,); ans++;
}
int main()
{
n=rdn();
val[]=-1e9-; val[]=1e9+;
fa[]=; c[][]=; tot=; rt=;
for(int i=,l,r;i<=n;i++)
{
l=rdn(); r=rdn();
solve(l,r);
}
printf("%d\n",ans);
return ;
}