CF809D Hitchhiking in the Baltic States-平衡树+DP
Statement
给出 \(n\) 个区间 \([l_i,r_i]\) 和 \(n\) 个未知数 \(a_1,a_2,\dots,a_n\)，现在你要确定这 \(n\) 个数，使得 \(a_i\in[l_i,r_i]\)，并且这个序列的最长严格上升子序列尽可能大，求这个最大值。
\(1 \leq n\leq 3\times 10^5\)，\(1 \leq l_i,r_i\leq 10^9\)。
Solution
好题！很妙，非常妙！
首先感觉就很想 dp，
但是 dp 的方程式又很难推出来。。。
对于最长严格上升子序列，
我们进行套路性的操作：
设 \(dp[j]\) 表示最长严格上升子序列的长度为 \(j\) 时，最后一位最小的值。
很容易发现，\(dp[j]\) 一定时单调递增的。
所以我们现在考虑加入每一个元素时的转移：
令当前的 \(l_i,r_i\) 分别为 \(l,r\)，每一次我们一定是从 \(dp[j-1]\) 转移到 \(dp[j]\)：
- 当 \(dp[j-1] \lt l\) 时，\(dp[j]=\min(dp[j],l)\)。
- 当 \(l \le dp[j-1] \lt r\) 时，\(dp[j]=\min(dp[j],dp[j-1]+1)\)。
- 当 \(dp[j-1]\ge r\) 时，\(dp[j]=dp[j]\) ，即不变。
于是我们得到了 \(O(n^2)\) 的做法。
现在考虑如何优化呢？（很难想到平衡树）
发现每一次 \(+1\) 一定是最优的，
我们现在考虑把整个数列看成一个整体，
对于操作 \(2\) ，我们可以发现其实就是相当于把区间 \([l,r-1]\) 里面的数都 \(+1\)，
然后再右移一位，
而这样做完了发现有两个位置出现了冲突：
- \(\lt l\) 的最大的数的后一位，发现这里本来是 \(\ge l\) 的最小的数，那经过一次变化后，这一位最有的一定是 \(l\)。
- 而对于后面冲突的 \(\ge r\) 的最小的数，它一定是不优的，直接删除。
这样的分析我们发现其实每一次操作就是在序列上面在 \(\lt l\) 的最大位置后面插入 \(l\)，将 \([l,r-1]\) 区间 \(+1\) ，再删除之前就 \(\ge r\) 的最小的数，
这些操作都可以用平衡树维护。
于是我们就可以用平衡树和 DP 完成此题，
而最后的答案就是平衡树的 \(siz\) 。
（没有一过呜呜呜）
#include <bits/stdc++.h>
using namespace std;
mt19937 rd(time(0));
const int N=3e5+5;
int n,l,r,idx=0,rt,x,y,z;
struct Treap{
int key,s[2],val,siz,tag;
}tr[N];
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
return x*f;
}
int nwnode(int v){
tr[++idx].val=v;
tr[idx].key=rd();
tr[idx].siz=1;
tr[idx].s[0]=tr[idx].s[1]=tr[idx].tag=0;
return idx;
}
#define lc(p) tr[p].s[0]
#define rc(p) tr[p].s[1]
void pu(int p){tr[p].siz=tr[lc(p)].siz+tr[rc(p)].siz+1;}
void pd(int p){
if(!p||!tr[p].tag) return ;
if(lc(p)) tr[lc(p)].tag+=tr[p].tag,tr[lc(p)].val+=tr[p].tag;
if(rc(p)) tr[rc(p)].tag+=tr[p].tag,tr[rc(p)].val+=tr[p].tag;
tr[p].tag=0;
}
void split(int p,int k,int &x,int &y){
if(!p){x=y=0;return;}
pd(p);
if(tr[p].val<=k) x=p,split(rc(p),k,rc(p),y);
else y=p,split(lc(p),k,x,lc(p));
pu(p);
}
int merge(int x,int y){
if(!x||!y) return (x|y);
pd(x);pd(y);
if(tr[x].key<tr[y].key){
tr[x].s[1]=merge(tr[x].s[1],y);
pu(x);return x;
}
else{
tr[y].s[0]=merge(x,tr[y].s[0]);
pu(y);return y;
}
}
int find(int x,int k){
if(!k) return 0;
while(233){
if(tr[lc(x)].siz>=k) x=lc(x);
else if(tr[lc(x)].siz+1<k) k-=tr[lc(x)].siz+1,x=rc(x);
else return x;
}
}
int pre(int val){
split(rt,val-1,x,y);
int res=find(x,tr[x].siz);
rt=merge(x,y);
return res;
}
int nxt(int val){
split(rt,val,x,y);
int res=find(y,1);
rt=merge(x,y);
return res;
}
void ins(int val){
split(rt,val,x,y);
rt=merge(x,merge(nwnode(val),y));
}
void del(int val){
split(rt,val,x,z);
split(x,val-1,x,y);
y=merge(tr[y].s[0],tr[y].s[1]);
rt=merge(x,merge(y,z));
}
void update(int l,int r){
split(rt,l-1,x,y);
split(y,r,y,z);
tr[y].tag++;tr[y].val++;
rt=merge(merge(x,y),z);
}
int main(){
/*2023.10.24 H_W_Y CF809D Hitchhiking in the Baltic States DP+Treap*/
n=read();
for(int i=1;i<=n;i++){
l=read();r=read();
if(i==1){ins(l);continue;}
int q=nxt(r-1);
update(l,r-1);
ins(l);
if(q) del(tr[q].val);
}
if(!rt) puts("0");
else printf("%d\n",tr[rt].siz);
return 0;
}
Conclusion
- 最长上升子序列：设 \(dp[j]\) 表示最长严格上升子序列的长度为 \(j\) 时，最后一位最小的值！！！
- dp 的优化可以考虑平衡树，将数列看作一个整体。