题解 P3968 【[TJOI2014]电源插排】

Froggy · 2020-01-08 11:49:23 · 题解

set,动态开点线段树¿¿¿ 为什么不挑战一下动态开点 \operatorname{FHQ \ Treap} ¿¿¿

这样写代码难度很高,但未尝不是锻炼代码能力的一种方法, [大雾] ~~(珂能我写复杂了,常数巨大,吸氧才过)~~

其实这道题csp2019前一天就写了一上午,写呱了,心态炸了,期末考试完了拐回头重构代码,终于A了

由于是动态开点平衡树,所以每个节点记录一个区间 (l,r)

len 为该节点代表的区间长度,即 r-l+1

siz 为以该节点为根的子树所构成的区间大小 (注意区分上面两个,否则写着写着就混淆了)

询问操作

好办,val 记录该节点被使用的插排个数, sum 以该节点为根的子树被使用的插排个数

更新节点信息的时候这样就好了

t[k].siz=t[ls].siz+t[rs].siz+t[k].len;
t[k].sum=t[ls].sum+t[rs].sum+t[k].val;

询问的时候把区间分裂出来输出sum

重点是----

插入/删除操作

要找到长度最大的连续一段空插座 (mxl,mxr)

需要维护 maxlen 即 mxr-mxl+1

和要插的位置mid 即 (mxl+mxr+1)/2

如果维护了这两个,那么就不需要维护mxl和mxr了.

lmax和rmax,即最左/右边连续空插座的个数

举个例子:

比如一段插座长这样:(1表示有电源插入,0表示空)

110100001000

那么lmax=0, rmax=3, maxlen=4 ,mid=(5+8+1)/2

要插入的位置就很显然了: t[root].mid

还需要开个map::vis方便下一次删除

现在考虑如何维护:

维护lmax和rmax很套路,不说了

分别取左右子树的maxlen的最大值

当t[k].val==0的时候还要特殊讨论:

跨节点k的一段空插座长度为 t[k].len+t[ls].rmax+t[rs].lmax

更新一下就好了啦~

inline void update(int k){
    #define ls t[k].ch[0]
    #define rs t[k].ch[1]
    t[k].siz=t[ls].siz+t[rs].siz+t[k].len;
    t[k].maxlen=0;
    t[k].sum=t[ls].sum+t[rs].sum+t[k].val;
    t[k].lmax=t[ls].lmax;
    t[k].rmax=t[rs].rmax;
    if(ls){//从左子树更新
        t[k].maxlen=t[ls].maxlen;
        t[k].mid=t[ls].mid;
    }
    if(t[k].val==0){ //跨左右子树讨论
        if(t[ls].sum==0){
            t[k].lmax=t[ls].lmax+t[k].len+t[rs].lmax;
        }
        if(t[rs].sum==0){
            t[k].rmax=t[ls].rmax+t[k].len+t[rs].rmax;
        }
        int len=t[k].len+t[ls].rmax+t[rs].lmax;
        if(len>=t[k].maxlen){
            t[k].maxlen=len;
            t[k].mid=(t[k].l-t[ls].rmax+t[k].r+t[rs].lmax+1)>>1;
        }
    }
    if(t[rs].maxlen>=t[k].maxlen){ //从右子树更新
        t[k].maxlen=t[rs].maxlen;
        t[k].mid=t[rs].mid;
    }
    #undef ls
    #undef rs
}

code:

#include<iostream>
#include<cstdio>
#include<map>
#include<cstdlib>
using namespace std;
#define N 100010
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<3)+(x<<1)+c-'0';
        c=getchar();
    }
    return x*f;
}
map<int,int> mp,vis;
int n,Q,root,cnt;
struct node{
    int ch[2],key,l,r,val,sum,siz,len;
    int mid,lmax,rmax,maxlen;
}t[N<<3];
inline int NewNode(int l,int r){
    int k=++cnt;
    t[k].key=rand();
    t[k].l=l,t[k].r=r;
    t[k].mid=(l+r+1)>>1;
    t[k].ch[0]=t[k].ch[1]=0;
    t[k].val=t[k].sum=0;
    t[k].maxlen=t[k].siz=t[k].len=t[k].lmax=t[k].rmax=r-l+1;
    mp[r]=k;
    return k; 
}
inline void update(int k){
    #define ls t[k].ch[0]
    #define rs t[k].ch[1]
    t[k].siz=t[ls].siz+t[rs].siz+t[k].len;
    t[k].maxlen=0;
    t[k].sum=t[ls].sum+t[rs].sum+t[k].val;
    t[k].lmax=t[ls].lmax;
    t[k].rmax=t[rs].rmax;
    if(ls){
        t[k].maxlen=t[ls].maxlen;
        t[k].mid=t[ls].mid;
    }
    if(t[k].val==0){
        if(t[ls].sum==0){
            t[k].lmax=t[ls].lmax+t[k].len+t[rs].lmax;
        }
        if(t[rs].sum==0){
            t[k].rmax=t[ls].rmax+t[k].len+t[rs].rmax;
        }
        int len=t[k].len+t[ls].rmax+t[rs].lmax;
        if(len>=t[k].maxlen){
            t[k].maxlen=len;
            t[k].mid=(t[k].l-t[ls].rmax+t[k].r+t[rs].lmax+1)>>1;
        }
    }
    if(t[rs].maxlen>=t[k].maxlen){
        t[k].maxlen=t[rs].maxlen;
        t[k].mid=t[rs].mid;
    }
    #undef ls
    #undef rs
}
int Merge(int l,int r){
    if(!l||!r)return l+r;
    if(t[l].key<t[r].key){
        t[l].ch[1]=Merge(t[l].ch[1],r);
        update(l);
        return l;
    }
    else{
        t[r].ch[0]=Merge(l,t[r].ch[0]);
        update(r);
        return r;
    }
}
void Split(int k,int data,int &l,int &r){
    if(!k){
        l=r=0;
        return;
    }
    if(t[k].r<=data){
        l=k;
        Split(t[k].ch[1],data,t[k].ch[1],r);
    }
    else{
        r=k;
        Split(t[k].ch[0],data,l,t[k].ch[0]);
    }
    update(k);
}
inline void New(int pos){
    int k=mp.lower_bound(pos)->second;
    int x=t[k].l,y=t[k].r;
    if(x==y&&x==pos)return;
    int l,p,r;
    Split(root,y,l,r);
    Split(l,x-1,l,p);
    mp.erase(t[k].r);
    if(pos>x){
        l=Merge(l,NewNode(x,pos-1));
    }
    if(y>pos){
        r=Merge(NewNode(pos+1,y),r);
    } 
    root=Merge(Merge(l,NewNode(pos,pos)),r);
}
inline int Query(int x,int y){
    New(x),New(y);
    int l,p,r;
    Split(root,y,l,r);
    Split(l,x-1,l,p);
    int ans=t[p].sum;
    root=Merge(Merge(l,p),r);
    return ans;
}
inline void Delete(int pos){
    int l,p,r;
    Split(root,pos,l,r);
    Split(l,pos-1,l,p);
    t[p].val=t[p].sum=0;
    t[p].mid=pos,t[p].maxlen=t[p].lmax=t[p].rmax=t[p].len;
    root=Merge(Merge(l,p),r);
}
inline void Change(int pos){
    New(pos);
    int l,p,r;
    Split(root,pos,l,r);
    Split(l,pos-1,l,p);
    t[p].val=t[p].sum=1;
    t[p].mid=t[p].maxlen=t[p].lmax=t[p].rmax=0;
    root=Merge(Merge(l,p),r);
}
int main(){
    n=read(),Q=read();
    root=NewNode(1,n);
    while(Q--){
        int x=read();
        if(x==0){
            int l=read(),r=read();
            printf("%d\n",Query(l,r));
        }
        else{
            if(vis.count(x)){
                Delete(vis[x]);
                vis.erase(x);
            }
            else{
                vis[x]=t[root].mid;
                Change(t[root].mid);
            }
        }
    }
    return 0;
}

Froggy's blog

题解 P3968 【[TJOI2014]电源插排】

询问操作

插入/删除操作

呱!!