Description
给出 \(n\) 个数 \(a_i\),每一个数有一个取值 \([l_i,r_i]\) ,你来确定每一个数,使得 \(LIS\) 最大
题面
Solution
按照平时做法,设 \(f[i]\) 表示 \(LIS\) 长为 \(i\) 时, \(LIS\) 结尾的最小值
考虑插入一个取值为 \([L,R]\) 可以更新的值
找到小于 \(L\) 的第一个数 \(p\) 和小于 \(R\) 的第一个数 \(q\)
那么 \(f[p+1]\) 可以更新为 \(L\) , \(i=[p+2,q]\) 都可以被更新为 \(f[i]=f[i-1]+1\)
实际上就是把数组右移,然后再区间加 \(1\)
平衡树维护一下,对应删除 \(q+1\) ,插入 \(f[p+1]=L\)
#include<bits/stdc++.h>
using namespace std;
template<class T>void gi(T &x){
int f;char c;
for(f=1,c=getchar();c<'0'||c>'9';c=getchar())if(c=='-')f=-1;
for(x=0;c<='9'&&c>='0';c=getchar())x=x*10+(c&15);x*=f;
}
const int N=3e5+10;
int n=0,ch[N][2],fa[N],rt=0,v[N],Q,la[N];
inline void mark(int x,int k){if(x)v[x]+=k,la[x]+=k;}
inline void pushdown(int x){
if(!la[x])return ;
mark(ch[x][0],la[x]);mark(ch[x][1],la[x]);la[x]=0;
}
inline void rotate(int x){
int y=fa[x];bool t=ch[y][1]==x;
ch[y][t]=ch[x][!t];
fa[ch[y][t]]=y;
ch[x][!t]=y;
fa[x]=fa[y];
if(fa[y])ch[fa[y]][ch[fa[y]][1]==y]=x;
fa[y]=x;
}
inline void Push(int x){
if(fa[x])Push(fa[x]);
pushdown(x);
}
inline void splay(int x,int goal){
Push(x);
while(fa[x]!=goal){
int y=fa[x],p=fa[y];
if(p==goal)rotate(x);
else if((ch[p][0]==y)==(ch[y][0]==x))rotate(y),rotate(x);
else rotate(x),rotate(x);
}
if(!goal)rt=x;
}
int ans=0;
inline int lower(int k){
int x=rt,ret=0;
while(x){
pushdown(x);
if(v[x]<k)ret=x,x=ch[x][1];
else x=ch[x][0];
}
return ret;
}
inline int nxt(int x){
splay(x,0);x=ch[x][1];
while(ch[x][0])x=ch[x][0];
return x;
}
inline void ins(int &x,int k,int last){
if(!x){v[x=++n]=k;fa[x]=last;splay(x,0);return ;}
pushdown(x);
ins(ch[x][k>v[x]],k,x);
}
inline void del(int x){
splay(x,0);
int p=ch[x][0],q=ch[x][1];
while(ch[p][1])p=ch[p][1];
while(ch[q][0])q=ch[q][0];
splay(p,0);splay(q,p);
ch[q][0]=fa[x]=0;
}
inline void solve(int l,int r){
int p=lower(l),q=lower(r),x=nxt(q);
if(p!=q){
splay(p,0);splay(x,p);
mark(ch[x][0],1);
}
if(x!=1)del(x),ans--;
ins(rt,l,0);ans++;
}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
cin>>Q;
v[++n]=1<<30;v[++n]=-(1<<30);fa[2]=1;ch[1][0]=2;rt=1;
for(int i=1,L,R;i<=Q;i++)gi(L),gi(R),solve(L,R);
cout<<ans<<endl;
return 0;
}