Jennie

转移的时候要知道区间最值

那何不利用线段树来解决

$O(nlogn)$

#include
#include
#include
#include
#include
using namespace std;
template
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<>1;
    if(L<=mid) add(ro<<1,l,mid,L,R,k);
    if(R>mid) add(ro<<1|1,mid+1,r,L,R,k);
    pushup(ro); 
}
int que(int ro,int l,int r,int L,int R){
    if(L<=l&&r<=R){
        return tr[ro];
    }
    int mid=(l+r)>>1;
    int ans=0;
    if(L<=mid)  ans=max(que(ro<<1,l,mid,L,R),ans);
    if(R>mid) ans=max(que(ro<<1|1,mid+1,r,L,R),ans);
    return ans;
}
int rr;
int main(){
    read(n);
    for(int i=1;i<=n;++i){
        read(sec[i].l);read(sec[i].r);
        sec[i].l+=2;
        sec[i].r+=2;
        rr=max(sec[i].r,rr);
    }
    sort(sec+1,sec+1+n);
    for(int i=1;i<=n;++i){
        f[sec[i].r]=max(que(1,1,rr,1,sec[i].l-1)+sec[i].r-sec[i].l+1,que(1,1,rr,sec[i].l,sec[i].r));
        //cout<