CF264E Roadside Trees 半年之后的又一遍题解

· · 题解

Link

之前写的题解

发现每次删除或加入影响的点数量很少，考虑暴力将这些点拆出来再依次加入。

那么分为下标和高度两维考虑，分别开一个线段树，这样才能够让每次删除与插入达到 \mathrm{O(\log n)} 的级别。

我用两个堆来存两维最小的 10 棵树的信息。需要时刻注意这两个堆之间的联动关系，如删除的时候要注意另一个堆中的元素要删除（我用了一个标记数组），插入的时候要同时插入另一个堆。

答案又另开了一个可删堆来存，非常唐。

实际上答案直接从这两棵线段树中任一棵查一个全局最大值即可。

代码写得比之前要好读一些。

code

const int N=2e5+50;

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;
            return;
        }
        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;
bool tag[N];
priority_queue<pir>he,at;//高度和下标的堆，插入和删除时要从这两个堆中找会影响到的数

pir tmp[15];int tot;

int f[N];
priority_queue<int>ans,del;

int lim;

void calc1(pir x){//插入高度最小的
    int i=x.fi,h=x.se;
    f[i]=T1.query(1,1,lim,i+1,lim)+1;
    T1.update(1,1,lim,i,f[i]);
    T2.update(1,1,lim,h,f[i]);
    ans.push(f[i]);
    he.push({-h,i});

}

void calc2(pir x){//插入下标最小的
    int i=x.fi,h=x.se;
    f[i]=T2.query(1,1,lim,h+1,lim)+1;
    T1.update(1,1,lim,i,f[i]);
    T2.update(1,1,lim,h,f[i]);
    ans.push(f[i]);
    at.push({-i,h});
}

int get_ans(){//获取答案，这里的答案用了一个堆，这个堆需要支持删除元素，所以又开了个del
    while(!del.empty()&&ans.top()==del.top())
        ans.pop(),del.pop();
    if(ans.empty())//WA on 2
        return 0;
    return ans.top();
}

signed main(){
    int n=read(),m=read();
    lim=m+10;
    for(int i=m;i>=1;i--){
        if(read()==1){
            int x=read(),height=read()+i;//偏移
            tot=0;
            while(!he.empty()&&-he.top().fi<height){//比自己矮的树
                if(!tag[he.top().se]){//没被删过
                    tmp[++tot].fi=he.top().se,tmp[tot].se=-he.top().fi;
                    del.push(f[tmp[tot].fi]);
                    T1.update(1,1,lim,tmp[tot].fi,0);
                    T2.update(1,1,lim,tmp[tot].se,0);//删除
                }
                he.pop();
            }
            tmp[++tot]={x,height};//插入
            at.push({-x,height});//另一个堆也要记得插入
            while(tot)//剩下的插回树上
                calc1(tmp[tot--]);
        }else{
            int x=read();
            tot=0;
            while(!at.empty()&&tot<x){
                tmp[++tot].fi=-at.top().fi,tmp[tot].se=at.top().se;//必定没被删除过
                del.push(f[tmp[tot].fi]);
                T1.update(1,1,lim,tmp[tot].fi,0);
                T2.update(1,1,lim,tmp[tot].se,0);//删除
                at.pop();
            }
            tag[tmp[tot].fi]=1;//删除标记
            f[tmp[tot].fi]=0;//清空
            tot--;//删掉这个元素
            while(tot)//插回来
                calc2(tmp[tot--]);
        }
        print(get_ans()),pc('\n');
    }
    return 0;
}