联[线段树]

题意

范围$1e18$

题解

首先看到范围这么大,肯定要离散化的,

发现最后最左面0位置只可能修改过的位置-1,+1,等,不可能在一段区间中间凭空出现

于是可以这样离散化

        if(l[i]!=1)
            lsh[++lsh[0]]=l[i]-1;
        lsh[++lsh[0]]=l[i];
        lsh[++lsh[0]]=r[i];
        lsh[++lsh[0]]=r[i]+1;

然后考虑如何维护

两种方法:

1.维护最左0出现位置,最左1出现位置

这样异或操作就swap一下就好了

我没打这种

2.维护区间0个数,

这样异或操作就转化成了区间长度-0个数

查询如果左子树有0优先走左子树,否则走右子树,递归到叶子

3.keduoli树水过

这里用的第2种方法

两种懒标记不可同时存在,

down

void down(ll x){
//    printf("l=%lld r=%lld tr[lson].f1=%lld tr[rson].f1=%lld\n",tr[x].l,tr[x].r,tr[x<<1].f1,tr[x<<1|1].f1);
    if(tr[x].f1){
        if(tr[x<<1].f2){
            tr[x<<1].f2=0;
            tr[x<<1].sum=tr[x<<1].len-tr[x<<1].sum;
        }
        if(tr[x<<1|1].f2){
            tr[x<<1|1].f2=0;
            tr[x<<1|1].sum=tr[x<<1|1].len-tr[x<<1|1].sum;
        }
        tr[x<<1].f1=tr[x].f1;
        tr[x<<1].sum=((tr[x].f1==2)?tr[x<<1].len:0);
        tr[x<<1|1].f1=tr[x].f1;
        tr[x<<1|1].sum=((tr[x].f1==2)?tr[x<<1|1].len:0);
    }
    else if(tr[x].f2){//区间异或
        if(tr[x<<1].f2){
            tr[x<<1].f2=0;
            tr[x<<1].sum=tr[x<<1].len-tr[x<<1].sum;
        }
        else if(tr[x<<1].f1==1){
            tr[x<<1].sum=tr[x<<1].len;
            tr[x<<1].f1=2;
            tr[x<<1].f2=0;
        }
        else if(tr[x<<1].f1==2){
            tr[x<<1].sum=0;
            tr[x<<1].f1=1;
            tr[x<<1].f2=0;
        }
        else tr[x<<1].f2=1,tr[x<<1].sum=tr[x<<1].len-tr[x<<1].sum;
        if(tr[x<<1|1].f2){
            tr[x<<1|1].f2=0;
            tr[x<<1|1].sum=tr[x<<1|1].len-tr[x<<1|1].sum;
        }
        else if(tr[x<<1|1].f1==1){
            tr[x<<1|1].sum=tr[x<<1|1].len;
            tr[x<<1|1].f1=2;
            tr[x<<1|1].f2=0;
        }
        else if(tr[x<<1|1].f1==2){
            tr[x<<1|1].sum=0;
            tr[x<<1|1].f1=1;
            tr[x<<1|1].f2=0;
        }
        else tr[x<<1|1].f2=1,tr[x<<1|1].sum=tr[x<<1|1].len-tr[x<<1|1].sum;
    }
//    printf("down*** f1=%lld f2=%lld lson.f2=%lld rson.f2=%lld  l=%lld r=%lld tr[x].sum=%lld lson l=%lld r=%lld sum=%lld rson l=%lld r=%lld sum=%lld\n",tr[x].f1,tr[x].f2,tr[x<<1].f2,tr[x<<1|1].f2,tr[x].l,tr[x].r,tr[x].sum,tr[x<<1].l,tr[x<<1].r,tr[x<<1].sum,tr[x<<1|1].l,tr[x<<1|1].r,tr[x<<1|1].sum);
//    printf("l=%lld r=%lld lson.f1=%lld f2=%lld sum=%lld l=%lld r=%lld rson.f1=%lld f2=%lld sum=%lld\n",tr[x<<1].l,tr[x<<1].r,tr[x<<1].f1,tr[x<<1].f2,tr[x<<1].sum,tr[x<<1|1].l,tr[x<<1|1].r,tr[x<<1|1].f1,tr[x<<1|1].f2,tr[x<<1|1].sum);
    tr[x].f1=0;
    tr[x].f2=0;

}

注意,这里区间修改因为两种懒标记不可同时存在,所以也要进行这种操作

可能两次都修改同一个区间,这样你上一个标记没下传,这一个标记就又来了

特殊处理一下

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define A 10010101
ll c[A],l[A],r[A],opt[A],now[A],lsh[A],yuan[A];
ll ans,canqj=1,rest,n,len;
struct node{
    ll l,r,f1,f2,len,sum,yu;
}tr[A];
void up(ll x){
    tr[x].sum=tr[x<<1].sum+tr[x<<1|1].sum;
//    printf("x.l=%lld x.r=%lld tr[x].sum=%lld\n",tr[x].l,tr[x].r,tr[x].sum);
}
void built(ll x,ll l,ll r){
    tr[x].l=l,tr[x].r=r;
    tr[x].len=r-l+1;
    if(l==r){
        tr[x].sum=1;
        tr[x].yu=lsh[l];
        return;
    }
    ll mid=(tr[x].l+tr[x].r)>>1;
    built(x<<1,l,mid);
    built(x<<1|1,mid+1,r);
    up(x);
}
void down(ll x){
//    printf("l=%lld r=%lld tr[lson].f1=%lld tr[rson].f1=%lld\n",tr[x].l,tr[x].r,tr[x<<1].f1,tr[x<<1|1].f1);
    if(tr[x].f1){
        if(tr[x<<1].f2){
            tr[x<<1].f2=0;
            tr[x<<1].sum=tr[x<<1].len-tr[x<<1].sum;
        }
        if(tr[x<<1|1].f2){
            tr[x<<1|1].f2=0;
            tr[x<<1|1].sum=tr[x<<1|1].len-tr[x<<1|1].sum;
        }
        tr[x<<1].f1=tr[x].f1;
        tr[x<<1].sum=((tr[x].f1==2)?tr[x<<1].len:0);
        tr[x<<1|1].f1=tr[x].f1;
        tr[x<<1|1].sum=((tr[x].f1==2)?tr[x<<1|1].len:0);
    }
    else if(tr[x].f2){//区间异或
        if(tr[x<<1].f2){
            tr[x<<1].f2=0;
            tr[x<<1].sum=tr[x<<1].len-tr[x<<1].sum;
        }
        else if(tr[x<<1].f1==1){
            tr[x<<1].sum=tr[x<<1].len;
            tr[x<<1].f1=2;
            tr[x<<1].f2=0;
        }
        else if(tr[x<<1].f1==2){
            tr[x<<1].sum=0;
            tr[x<<1].f1=1;
            tr[x<<1].f2=0;
        }
        else tr[x<<1].f2=1,tr[x<<1].sum=tr[x<<1].len-tr[x<<1].sum;
        if(tr[x<<1|1].f2){
            tr[x<<1|1].f2=0;
            tr[x<<1|1].sum=tr[x<<1|1].len-tr[x<<1|1].sum;
        }
        else if(tr[x<<1|1].f1==1){
            tr[x<<1|1].sum=tr[x<<1|1].len;
            tr[x<<1|1].f1=2;
            tr[x<<1|1].f2=0;
        }
        else if(tr[x<<1|1].f1==2){
            tr[x<<1|1].sum=0;
            tr[x<<1|1].f1=1;
            tr[x<<1|1].f2=0;
        }
        else tr[x<<1|1].f2=1,tr[x<<1|1].sum=tr[x<<1|1].len-tr[x<<1|1].sum;
    }
//    printf("down*** f1=%lld f2=%lld lson.f2=%lld rson.f2=%lld  l=%lld r=%lld tr[x].sum=%lld lson l=%lld r=%lld sum=%lld rson l=%lld r=%lld sum=%lld\n",tr[x].f1,tr[x].f2,tr[x<<1].f2,tr[x<<1|1].f2,tr[x].l,tr[x].r,tr[x].sum,tr[x<<1].l,tr[x<<1].r,tr[x<<1].sum,tr[x<<1|1].l,tr[x<<1|1].r,tr[x<<1|1].sum);
//    printf("l=%lld r=%lld lson.f1=%lld f2=%lld sum=%lld l=%lld r=%lld rson.f1=%lld f2=%lld sum=%lld\n",tr[x<<1].l,tr[x<<1].r,tr[x<<1].f1,tr[x<<1].f2,tr[x<<1].sum,tr[x<<1|1].l,tr[x<<1|1].r,tr[x<<1|1].f1,tr[x<<1|1].f2,tr[x<<1|1].sum);
    tr[x].f1=0;
    tr[x].f2=0;

}
void seg_add(ll x,ll l,ll r,ll val){
//    printf("l=%lld r=%lld tr[x].l=%lld tr[x].r=%lld\n",l,r,tr[x].l,tr[x].r);

    if(tr[x].l>=l&&tr[x].r<=r){
        if(val==3){//异或
            if(tr[x].f2){
                tr[x].f2=0;
                tr[x].sum=tr[x].len-tr[x].sum;
            }
            else if(tr[x].f1==1){
                tr[x].sum=tr[x].len;
                tr[x].f1=2;
                tr[x].f2=0;
            }
            else if(tr[x].f1==2){
                tr[x].sum=0;
                tr[x].f1=1;
                tr[x].f2=0;
            }
            else tr[x].f2=1,tr[x].sum=tr[x].len-tr[x].sum;
        }
        else if(val==1){//区间赋值1
            tr[x].sum=0;
            tr[x].f1=1;
            tr[x].f2=0;
        }
        else if(val==2){
            tr[x].sum=tr[x].len;
            tr[x].f1=2;
            tr[x].f2=0;
        }
//        printf("havefindit l=%lld r=%lld val=%lld val=%lld\n",tr[x].l,tr[x].r,tr[x].f1,val);
        return ;
    }
    if(tr[x].f1||tr[x].f2) down(x);
    ll mid=(tr[x].l+tr[x].r)>>1;
    if(mid>=l)seg_add(x<<1,l,r,val);
    if(mid<r) seg_add(x<<1|1,l,r,val);
    up(x);
}
void query(ll x){
    if(tr[x].l==tr[x].r){
        ans=lsh[tr[x].l];
        return ;
    }
//    printf("query l=%lld r=%lld f1=%lld f2=%lld\n",tr[x].l,tr[x].r,tr[x].f1,tr[x].f2);
    if(tr[x].f1||tr[x].f2) down(x);
    if(tr[x<<1].sum) query(x<<1);
    else query(x<<1|1);
    up(x);
}
void check(ll x){
//    printf("l=%lld r%lld f1=%lld f2=%lld sum=%lld\n",tr[x].l,tr[x].r,tr[x].f1,tr[x].f2,tr[x].sum);
    if(tr[x].l==tr[x].r) return ;
    check(x<<1);
    check(x<<1|1);
}
int main(){
    scanf("%lld",&n);
    lsh[++lsh[0]]=1;
    for(ll i=1;i<=n;i++){
        scanf("%lld%lld%lld",&opt[i],&l[i],&r[i]);
        if(l[i]!=1)
            lsh[++lsh[0]]=l[i]-1;
        lsh[++lsh[0]]=l[i];
        lsh[++lsh[0]]=r[i];
        lsh[++lsh[0]]=r[i]+1;
    }
    sort(lsh+1,lsh+lsh[0]+1);
    len=unique(lsh+1,lsh+lsh[0]+1)-lsh-1;
//    for(ll i=1;i<=lsh[0];i++){
//        printf("lsh[i]=%lld len=%lld\n",lsh[i],len);
//    }
    for(ll i=1;i<=n;i++){
        l[i]=lower_bound(lsh+1,lsh+len+1,l[i])-lsh;
        r[i]=lower_bound(lsh+1,lsh+len+1,r[i])-lsh;
//        printf("l=%lld r=%lld\n",l[i],r[i]);
    }
    built(1,1,len);
    for(ll i=1;i<=n;i++){
        seg_add(1,l[i],r[i],opt[i]);
        query(1);
//        check(1);
        printf("%lld\n",ans);
    }
}

View Code