【CF809D】Hitchhiking in the Baltic States
题意：给你n个区间[li,ri]，让你选出从中一个子序列，然后在子序列的每个区间里都选择一个tj，满足$t_1<t_2<...<t_{len}$。最大化这个子序列的长度。
$1\le n\le 3\cdot 10^5,1\le l\le r \le 10^9$
题解：我们用dp[i]表示在当前情况下，选择的最后一个$t\le i$时，最多能选多少个区间。然后我们加入每个区间，同时维护所有的dp值。
当加入区间[l,r]时，首先$dp[i]=max(dp[i],dp[i-1]+1),1\le l \le r$，又因为$dp[i]\le dp[i-1]+1$，所以必然会更新，我们用平衡树直接将区间平移一段，再区间+1即可。然后$dp[i]=max(dp[i],dp[r]+1),i>r$，我们可以在平衡树上找到最后一个dp[i]=dp[r]的位置，然后进行区间+1。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn=300010;
int n,tot,pre,nxt,ans,rt;
struct node
{
int ch[2],fa,tag,sv,siz;
}s[maxn<<2];
inline void pushup(int x)
{
s[x].siz=s[s[x].ch[0]].siz+s[s[x].ch[1]].siz+1;
}
inline void upd(int x,int v)
{
if(x) s[x].tag+=v,s[x].sv+=v;
}
inline void pushdown(int x)
{
if(s[x].tag) upd(s[x].ch[0],s[x].tag),upd(s[x].ch[1],s[x].tag),s[x].tag=0;
}
inline void rotate(int x,int &k)
{
int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);
if(y==k) k=x;
else s[z].ch[y==s[z].ch[1]]=x;
s[x].fa=z,s[y].fa=x,s[y].ch[d]=s[x].ch[d^1];
if(s[x].ch[d^1]) s[s[x].ch[d^1]].fa=y;
s[x].ch[d^1]=y;
pushup(y),pushup(x);
}
inline void splay(int x,int &k)
{
while(x!=k)
{
int y=s[x].fa,z=s[y].fa;
if(y!=k)
{
if((x==s[y].ch[0])^(y==s[z].ch[0])) rotate(x,k);
else rotate(y,k);
}
rotate(x,k);
}
}
int find(int x,int y)
{
pushdown(x);
if(y<=s[s[x].ch[0]].siz) return find(s[x].ch[0],y);
else if(y>s[s[x].ch[0]].siz+1) return find(s[x].ch[1],y-s[s[x].ch[0]].siz-1);
return x;
}
void getpre(int x,int y)
{
if(!x) return ;
pushdown(x);
if(s[x].sv<y) pre=x,getpre(s[x].ch[1],y);
else getpre(s[x].ch[0],y);
}
int build(int l,int r)
{
if(l>r) return 0;
int x=(l+r)>>1;
s[x].siz=r-l+1,s[x].ch[0]=build(l,x-1),s[x].ch[1]=build(x+1,r),s[x].sv=1<<30;
if(s[x].ch[0]) s[s[x].ch[0]].fa=x;
if(s[x].ch[1]) s[s[x].ch[1]].fa=x;
pushup(x);
return x;
}
void dfs(int x,int y)
{
if(!x) return ;
pushdown(x);
if(s[x].sv<(1<<30))
{
ans=max(ans,y+s[s[x].ch[0]].siz);
dfs(s[x].ch[1],y+s[s[x].ch[0]].siz+1);
}
else dfs(s[x].ch[0],y);
}
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-') f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+(gc^'0'),gc=getchar();
return ret*f;
}
int main()
{
n=rd();
rt=build(1,n+3);
s[0].sv=s[1].sv=0;
int i,a,b,x,y,z,rx,ry,p,q;
for(i=1;i<=n;i++)
{
a=rd(),b=rd();
getpre(rt,a),x=pre,getpre(rt,b),y=pre;
splay(y,rt),ry=s[s[y].ch[0]].siz+1;
q=find(y,ry+2),splay(q,s[y].ch[1]);
z=s[q].ch[0],s[q].ch[0]=0,pushup(q),pushup(y);
s[z].sv=a;
splay(x,rt),rx=s[s[x].ch[0]].siz+1;
p=find(x,rx+1),splay(p,s[x].ch[1]);
s[p].ch[0]=z,s[z].fa=p,pushup(p),pushup(x);
splay(z,rt),splay(q,s[z].ch[1]);
upd(s[q].ch[0],1);
}
dfs(rt,0);
printf("%d",ans);
return 0;
}//20 1 2 4 13 17 18 24 28 16 34 5 25 1 23 8 26 27 36 1 27 3 9 15 29 8 16 9 28 13 34 7 11 3 7 12 40 20 28 10 33