CF264E Roadside Trees

· · 个人记录

考虑dp。

有一个很重要的信息是 h,x\leq 10 和任何时刻不存在高度相等的树。

发现一棵树刚种下比它矮的树和砍掉时左边的树都很少，所以设 f_i 表示下标为 i 的位置开头的最长上升子序列数量。

发现种下和砍掉相当于交换了下标和高度，基本是相同的。

只考虑种下。

把他的下标和高度（加上偏移值所以高度不变）一棵树会从它右上角一块转移来。

但是不会写树套树所以只考虑x这一维，然后把y上不符合要求的点在x对应的线段树上删掉。

若y为高度的话，那么在y上不符合条件的点最多有9个。

（也即在刚种下这棵树时比这棵树还矮的树的棵数

直接暴力删，新种下的树通过x维线段树求解，然后倒序更新这些不符合条件的点（可能被新种的树更新）。

砍树就是在y维的线段树上删，求解，再倒序更新。

开两棵线段树。记录一下当前时刻实际高度（不包含偏移值）为 [1,10] 的树的下标（用于种树时暴力删），还要记录一下所有种着树的下标（用与砍树时暴力删）。

code

const int N=4e5+50,d=2e5+15;

struct Seg_Tree{
    int t[N<<2];
    void pushup(int x){t[x]=max(t[ls],t[rs]);}
    void update(int x,int l,int r,int c,int a){//单点改
        if(l==r)
            t[x]=a;
        else{
            if(c<=mid)
                update(ls,l,mid,c,a);
            else
                update(rs,mid+1,r,c,a);
            pushup(x);
        }
    }
    int query(int x,int l,int r,int L,int R){//区间查最大值
        if(L<=l&&r<=R)
            return t[x];
        int mx=0;
        if(L<=mid)
            mx=max(mx,query(ls,l,mid,L,R));
        if(R>mid)
            mx=max(mx,query(rs,mid+1,r,L,R));
        return mx;
    }
}T1,T2;

int id[15];//实际高度为[1,10]的树

set<int> s;//所有种着树的下标位置

struct node{
    int x,h;
}a[N];//下标和带偏移值的高度

int num[N];//找下标对应的树

int stk[15];

signed main(){
    int n=read(),q=read();
    for(int k=1;k<=q;k++){
        for(int i=10;i>=1;i--)
            id[i+1]=id[i];//实际高度增加
        id[1]=0;
        if(read()==1){
            int x=read(),h=read();
            a[k]={x,h-k};
            s.insert(x);
            id[h]=k;
            num[x]=k;
            for(int i=1;i<h;i++){
                if(!id[i])
                    continue;
                T1.update(1,1,n+1,a[id[i]].x,0);
                T2.update(1,1,2*d,a[id[i]].h+d,0);//暴力删
            }
            for(int i=h;i>=1;i--){
                if(!id[i])
                    continue;
                int tmp=T1.query(1,1,n+1,a[id[i]].x+1,n+1)+1;
                T1.update(1,1,n+1,a[id[i]].x,tmp);
                T2.update(1,1,2*d,a[id[i]].h+d,tmp);//再更新
            }
        }else{
            int x=read(),cnt=0;
            for(int i:s){
                if(cnt==x)
                    break;
                cnt++;
                stk[cnt]=i;
                T1.update(1,1,n+1,i,0);
                T2.update(1,1,2*d,a[num[i]].h+d,0);//暴力删
            }
            s.erase(stk[cnt]);//砍树
            for(int i=1;i<=10;i++)
                if(id[i]==num[stk[cnt]])
                    id[i]=0;//更新实际高度数组（可能看了一棵实际高度小于等于10的树
            cnt--;
            while(cnt){
                int i=stk[cnt];
                int tmp=T2.query(1,1,2*d,a[num[i]].h+d+1,2*d)+1;
                T1.update(1,1,n+1,i,tmp);
                T2.update(1,1,2*d,a[num[i]].h+d,tmp);//再更新
                cnt--;
            }
        }
        print(T1.query(1,1,n+1,1,n+1)),pc('\n');
    }
    return 0;
}