[CF817F] MEX Queries (线段树+离散化)

题目链接

题解

一道线段树模板题，离散化需要注意下，居然交了10次，丢人……

细节还是很多的，最近都在写平衡树，一开始把线段树写成和权值树那样的分治方法了orz

代码

#include<bits/stdc++.h>
#define lt p<<1
#define rt p<<1|1
using namespace std;
const int MAXN=500005;
typedef long long ll;//全开ll吧
ll l[MAXN],r[MAXN],ls[MAXN<<2],opt[MAXN];
ll n,cnt;
struct SegTree{
    ll l,r;
    ll val,tag;
}t[MAXN<<3];

ll read(){
    ll x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

inline void update(int p){
    t[p].val=t[lt].val+t[rt].val;
}

inline void pushdown(int p){
    ll mid=((t[p].l+t[p].r)>>1);
    if(t[p].tag==1){
        t[lt].val=mid-t[p].l+1;
        t[rt].val=t[p].r-mid;
        t[lt].tag=1,t[rt].tag=1;
    }
    if(t[p].tag==0){
        t[lt].val=t[rt].val=0;
        t[lt].tag=0,t[rt].tag=0;
    }
    t[p].tag=-1;
}

void build(int p,ll l,ll r){//建树
    t[p].l=l;t[p].r=r;ll mid=(l+r)>>1;
    if(l==r){
        t[p].tag=0;//初始的时候全是0（其实这里为-1也行）
        return;
    }
    build(lt,l,mid);build(rt,mid+1,r);
}

void change(int p,ll L,ll R,int type){
    if(L<=t[p].l&&R>=t[p].r){
        t[p].tag=type;t[p].val=(t[p].r-t[p].l+1)*type;return ;//打标记，更新值，如果为1就是区间长度，否则为0
    }
    pushdown(p);
    ll mid=(t[p].l+t[p].r)>>1;
    if(L<=mid)change(lt,L,R,type);
    if(R>mid)change(rt,L,R,type);
    update(p);
}

void rev(int p,ll L,ll R){
    if(t[p].l>=L&&t[p].r<=R&&t[p].tag!=-1){
        t[p].tag^=1;t[p].val=t[p].r-t[p].l+1-t[p].val;return;//翻转，更新标记，值也“翻转”
    }
    pushdown(p);
    ll mid=(t[p].l+t[p].r)>>1;
    if(L<=mid)rev(lt,L,R);
    if(R>mid)rev(rt,L,R);
    update(p);
}

ll query(int p){
    if(t[p].l==t[p].r)return t[p].l;
    ll mid=(t[p].l+t[p].r)>>1;
    pushdown(p);
    if(t[lt].val<mid-t[p].l+1)return query(lt);//如果左子树还有0，往左子树找
    else return query(rt);
}

int main(){
    n=(int)read();
    ls[++cnt]=1;//！！！防止左边爆炸！
    for(int i=1;i<=n;i++){
        opt[i]=read();l[i]=read();r[i]=read();
        ls[++cnt]=l[i];ls[++cnt]=r[i];ls[++cnt]=r[i]+1;//！！！防止右边爆炸（其实只要加一个max(r[i])+1就行
    }
    build(1,1,cnt);
    sort(ls+1,ls+cnt+1);
    ll len=unique(ls+1,ls+cnt+1)-ls-1;
    for(int i=1;i<=n;i++){
        ll x=lower_bound(ls+1,ls+len+1,l[i])-ls;
        ll y=lower_bound(ls+1,ls+len+1,r[i])-ls;
        if(opt[i]==1)change(1,x,y,1);
        else if(opt[i]==2)change(1,x,y,0);
        else rev(1,x,y);
        printf("%lld\n",ls[query(1)]);
    }
    return 0;
}

100

#include<bits/stdc++.h>

#define lt p<<1

#define rt p<<1|1

using namespace std;

const int MAXN=500005;

typedef long long ll;//全开ll吧

ll l[MAXN],r[MAXN],ls[MAXN<<2],opt[MAXN];

ll n,cnt;

struct SegTree{

ll l,r;

ll val,tag;

}t[MAXN<<3];

ll read(){

ll x=0,f=1;char ch=getchar();

while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}

while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

inline void update(int p){

t[p].val=t[lt].val+t[rt].val;

}

inline void pushdown(int p){

ll mid=((t[p].l+t[p].r)>>1);

if(t[p].tag==1){

t[lt].val=mid-t[p].l+1;

t[rt].val=t[p].r-mid;

t[lt].tag=1,t[rt].tag=1;

}

if(t[p].tag==0){

t[lt].val=t[rt].val=0;

t[lt].tag=0,t[rt].tag=0;

}

t[p].tag=-1;

}

void build(int p,ll l,ll r){//建树

t[p].l=l;t[p].r=r;ll mid=(l+r)>>1;

if(l==r){

t[p].tag=0;//初始的时候全是0（其实这里为-1也行）

return;

}

build(lt,l,mid);build(rt,mid+1,r);

}

void change(int p,ll L,ll R,int type){

if(L<=t[p].l&&R>=t[p].r){

t[p].tag=type;t[p].val=(t[p].r-t[p].l+1)*type;return ;//打标记，更新值，如果为1就是区间长度，否则为0

}

pushdown(p);

ll mid=(t[p].l+t[p].r)>>1;

if(L<=mid)change(lt,L,R,type);

if(R>mid)change(rt,L,R,type);

update(p);

}

void rev(int p,ll L,ll R){

if(t[p].l>=L&&t[p].r<=R&&t[p].tag!=-1){

t[p].tag^=1;t[p].val=t[p].r-t[p].l+1-t[p].val;return;//翻转，更新标记，值也“翻转”

}

pushdown(p);

ll mid=(t[p].l+t[p].r)>>1;

if(L<=mid)rev(lt,L,R);

if(R>mid)rev(rt,L,R);

update(p);

}

ll query(int p){

if(t[p].l==t[p].r)return t[p].l;

ll mid=(t[p].l+t[p].r)>>1;

pushdown(p);

if(t[lt].val<mid-t[p].l+1)return query(lt);//如果左子树还有0，往左子树找

else return query(rt);

}

int main(){

n=(int)read();

ls[++cnt]=1;//！！！防止左边爆炸！

for(int i=1;i<=n;i++){

opt[i]=read();l[i]=read();r[i]=read();

ls[++cnt]=l[i];ls[++cnt]=r[i];ls[++cnt]=r[i]+1;//！！！防止右边爆炸（其实只要加一个max(r[i])+1就行

}

build(1,1,cnt);

sort(ls+1,ls+cnt+1);

ll len=unique(ls+1,ls+cnt+1)-ls-1;

for(int i=1;i<=n;i++){

ll x=lower_bound(ls+1,ls+len+1,l[i])-ls;

ll y=lower_bound(ls+1,ls+len+1,r[i])-ls;

if(opt[i]==1)change(1,x,y,1);

else if(opt[i]==2)change(1,x,y,0);

else rev(1,x,y);

printf("%lld\n",ls[query(1)]);

}

return 0;

}

题解

代码

发送评论 编辑评论

发送评论编辑评论