题解：CF2121H Ice Baby

· · 题解

题解区怎么只有离散化线段树，这里给个动态开点线段树做法，复杂度是 \mathcal O(n\log w) 的。

Problem

题目很简单，a_i 可以从 [l_i,r_i] 中选择，问你最后最大的最长不降子序列。

Solution

设状态 f_i 表示当前最后一个数字（最大的数字）为 i ，转移有两种：

  1. 能取最小肯定贪心地取最小的 l_i 更优 f_{l_i} 可以从小于 l_i 的地方转移过来，即：

  2. 从同样的数字转移肯定不增加更优所以：

    f_j\gets f_j+1 ,{j\in [l_i,r_i]}

于是，就可以暴力地愉快地线段树了。

我们需要一个区间 +1 操作和一个单点修改操作。

因为懒得离散化，所以直接动态开点了。

注意：使用线段树询问 1\sim l_i-1 最大值时可能会越界，需要特判一下，否则会 RE。

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define all(x) x.begin(),x.end()
using namespace std;
template<typename T_>void Max(T_&x,const T_&y){if(y>x)x=y;}
template<typename T_>void Min(T_&x,const T_&y){if(y<x)x=y;}
template<typename T_>void operator+=(vector<T_>&x,const T_&y){x.push_back(y);}
template<typename T_>void operator--(vector<T_>&x){x.pop_back();}
const int N=2e5+7,_=1e9;
int T,n,mx[N*64],lzy[N*64],ls[N*64],rs[N*64],cnt,rot;//开大点准没错
void f(int rt,int x){mx[rt]+=x,lzy[rt]+=x;}
void push_down(int rt){
    if(!lzy[rt])return;
    if(!ls[rt])ls[rt]=++cnt;//这里要开点，否则信息会丢失
    if(!rs[rt])rs[rt]=++cnt;
    f(ls[rt],lzy[rt]),f(rs[rt],lzy[rt]);
    lzy[rt]=0;
}
void push_up(int rt){mx[rt]=max(mx[ls[rt]],mx[rs[rt]]);}
void update(int x,int l,int r,int k,int&rt){
    if(!rt)rt=++cnt;
    if(l==r)return Max(mx[rt],k);
    int mid=(l+r)>>1;push_down(rt);
    if(x<=mid)update(x,l,mid,k,ls[rt]);
    else update(x,mid+1,r,k,rs[rt]);
    push_up(rt);
}
void add(int L,int R,int l,int r,int k,int&rt){
    if(!rt)rt=++cnt;
    if(L<=l&&r<=R)return f(rt,k);
    int mid=(l+r)>>1;push_down(rt);
    if(L<=mid)add(L,R,l,mid,k,ls[rt]);
    if(R>mid)add(L,R,mid+1,r,k,rs[rt]);
    push_up(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(L>R||!rt)return 0;//特判
    if(L<=l&&r<=R)return mx[rt];
    int mid=(l+r)>>1,res=0;push_down(rt);
    if(L<=mid)Max(res,query(L,R,l,mid,ls[rt]));
    if(R>mid)Max(res,query(L,R,mid+1,r,rs[rt]));
    return res;
}
void work(){
    cin>>n;
    for(int i=1,l,r,x;i<=n;i++){
        cin>>l>>r;
        x=query(1,l-1,1,_,rot);
        add(l,r,1,_,1,rot);//区间加
        update(l,1,_,x+1,rot);//单点修改
        cout<<query(1,_,1,_,rot)<<' ';//询问 max
    }
    cout<<'\n';
    for(int i=0;i<=cnt;i++)ls[i]=rs[i]=lzy[i]=mx[i]=0;
    cnt=rot=0;//清空用过的就行
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)work();
    return 0;
}