小L的线段树

链接

这道题考察的还是线段树,乍一看舍去了好多线段树相关的性质,实则没有

比如懒标记,其实还是在的

当某个节点被破坏时,此时我们需要向下查询,耗时间,所以可以使用懒标记(与普通懒标记不同的是,这个是向上传播的)

也就是在destroy函数中向上更新懒标记(定义为sum,节点摧毁时有效,否则跳过)

#include<iostream>
using namespace std;
const int N=1e6+5;
int n;
struct node{
    int l,r;
    int des;
    int sum;
}tr[N<<2];

void build(int u,int l,int r){
    tr[u]={l,r,0,0};
    if(l==r) return;
    int mid=(l+r)>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}

int query(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r) {
        if(tr[u].des) return tr[u].sum;
        return 1;
    }
    int res=0;
    if(!tr[u].des) res++;
    int mid=(tr[u].l+tr[u].r)>>1;
    if(l<=mid) res+=query(u<<1,l,r);
    if(r>mid) res+=query(u<<1|1,l,r);
    return res;
}

void destroy(int u,int l,int r){
    if(tr[u].l>=l&&tr[u].r<=r){
        tr[u].des=1;
        tr[u].sum=query(u<<1,tr[u<<1].l,tr[u<<1].r)+
            query(u<<1|1,tr[u<<1|1].l,tr[u<<1|1].r);
       
        return;
    }
    int mid=(tr[u].l+tr[u].r)>>1;
    if(l<=mid) destroy(u<<1,l,r);
    if(r>mid) destroy(u<<1|1,l,r);
    //在这里更新sum,前提是des有效
    if(tr[u].des) {
        tr[u].sum = query(u<<1, tr[u<<1].l, tr[u<<1].r) + 
                    query(u<<1|1, tr[u<<1|1].l, tr[u<<1|1].r);
    }
}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    build(1,1,n);
    while(n--){
        int op,l,r;
        cin>>op>>l>>r;
        if(op==1) destroy(1,l,r);
        else cout<<query(1,l,r)<<'\n';
    }
}