题解 CF817F 【MEX Queries】

Froggy · 2020-01-26 22:15:27 · 题解

动态开点平衡树,她不香么?

我看见清一色的离散化+线段树,为毛我第一想法是动态开点?

用 \operatorname{FHQ\ Treap} 更好处理一些

动态开点会使pushdown极其简短

安利另一道动态开点平衡树的题P3968 + 题解 ,P3968显然比这道题要复杂一些..(但其实只要思路清晰也不难)

看题解之前,首先要保证会写 \operatorname{FHQ\ Treap}

对于平衡树中的每个节点记录所代表的区间 [l,r] ,以及区间里的数的值num ,反转标记rev,最左侧的0/1: mn[0/1] (如果不存在0/1就设置为inf) 和以它为根的子树所代表的区间长度 siz (别忘开long long哦)

同时用一个map记录右端点为r的节点编号,方便之后的动态开点

这里重点讲如何开点:

比如搞要在 [L,R] 这个区间进行操作,那么就分别在 L,R 的位置新开点

假设开点的位置为 pos

首先要找到 pos 在平衡树的哪个节点的区间之中,即在平衡树中找到一个节点的区间 [l,r] 满足: l \leq pos \leq r

这个好办,直接在map里面lower_bound即可

然后就可以拆成 [l,pos-1],[pos,pos],[pos+1,r] 三个区间,新建三个节点然后再合并回去即可(具体见代码)

当然要先判断一下 pos>l 和 r>pos

别忘了删除原来的节点,更新map!!!

开点讲完了,还有一些细节:

区间反转的时候还要 swap(mn[0],mn[1]);

update的时候很套路就不详细说了,更新mn[0/1]时直接在左右子树里取min即可

code:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<map>
using namespace std;
#define N 200010
typedef long long ll;
const ll inf=1LL<<61;
map<ll,int> mp;//开个map记录平衡树中右端点为r的节点编号
inline ll read(){
    ll 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;
}
int m,root,cnt=0;
struct node{
    int key,num,ch[2],rev;
    ll mn[2],l,r,siz;
    bool Rev(){//弄个成员函数进行区间反转
        num^=1;
        rev^=1;
        swap(mn[0],mn[1]);
    }
}t[N<<4];
int NewNode(int num,ll l,ll r){//建新节点
    int k=++cnt; 
    t[k].num=num;
    t[k].l=l,t[k].r=r;
    t[k].siz=r-l+1;
    t[k].key=rand();
    t[k].ch[0]=t[k].ch[1]=0;
    if(num==0){
        t[k].mn[0]=l;
        t[k].mn[1]=inf;
    }
    else{
        t[k].mn[0]=inf;
        t[k].mn[1]=l;
    }
    mp[r]=k;
    return k;
}
void pushdown(int k){//下放标记
    if(t[k].rev){
        t[t[k].ch[0]].Rev();
        t[t[k].ch[1]].Rev();
        t[k].rev=0;
    }
}
void update(int k){//更新节点信息
    t[k].mn[0]=t[k].mn[1]=inf;
    t[k].siz=t[t[k].ch[0]].siz+t[t[k].ch[1]].siz+t[k].r-t[k].l+1;
    if(t[k].num==0){
        t[k].mn[0]=t[k].l;
    }
    else{
        t[k].mn[1]=t[k].l;
    }
    if(t[k].ch[0]){
        for(int i=0;i<=1;i++)
        t[k].mn[i]=min(t[k].mn[i],t[t[k].ch[0]].mn[i]);
    }
    if(t[k].ch[1]){
        for(int i=0;i<=1;i++)
        t[k].mn[i]=min(t[k].mn[i],t[t[k].ch[1]].mn[i]);
    }
}
void Split(int k,ll data,int &l,int &r){
    if(!k){
        l=r=0;
        return;
    }
    pushdown(k);
    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);
}
int Merge(int l,int r){
    if(!l||!r)return l+r;
    pushdown(l),pushdown(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 del(int k){;
    mp.erase(mp.lower_bound(t[k].r));
    if(t[k].ch[0])del(t[k].ch[0]);
    if(t[k].ch[1])del(t[k].ch[1]);
}
void New(ll pos){//开点
    int k=mp.lower_bound(pos)->second;
    int l=0,r=0,p=0;
    int num=t[k].num;
    ll x=t[k].l,y=t[k].r;
    if(x==y&&x==pos)return;
    Split(root,y,l,r);
    Split(l,x-1,l,p);
    del(p);
    if(pos>x){
        l=Merge(l,NewNode(t[k].num,x,pos-1));
    }
    if(y>pos){
        r=Merge(NewNode(t[k].num,pos+1,y),r);
    }
    root=Merge(l,Merge(NewNode(t[k].num,pos,pos),r));
}
void Change(ll x,ll y,int num){
    int l=0,p=0,r=0;
    New(x),New(y);//先开点
    Split(root,y,l,r);
    Split(l,x-1,l,p);
    del(p);
    root=Merge(l,Merge(NewNode(num,x,y),r));
}
void Rev(ll x,ll y){
    int l=0,p=0,r=0;
    New(x),New(y);//先开点
    Split(root,y,l,r);
    Split(l,x-1,l,p);
    t[p].Rev();
    root=Merge(l,Merge(p,r));
}
int main(){
    srand(time(0));
    m=read();
    root=Merge(root,NewNode(0,1,2000000000000000000LL));//一开始开一个大区间
    for(int i=1;i<=m;i++){
        int opt=read();
        ll l=read(),r=read();
        if(opt==1){
            Change(l,r,1);
        }
        else if(opt==2){
            Change(l,r,0);
        }
        else{
            Rev(l,r);//1<->0
        }
        printf("%lld\n",t[root].mn[0]);//直接从根查询即可
    }
    return 0;
}

Froggy's blog

题解 CF817F 【MEX Queries】

呱!!