求助,动态开点线段树
查看原帖
求助,动态开点线段树
661913
liwenxi1145144444楼主2024/11/12 11:47
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,cnt,rt;
struct node{
    int l,r,w,lazy=-1;
}tree[9000005];
inline void push_down(int k,int dl,int dr){
    if(tree[k].lazy!=-1){
        int mid=(dl+dr)>>1;
        if(!tree[k].l){
            cnt++;
            tree[k].l=cnt;
        }
        if(!tree[k].r){
            cnt++;
            tree[k].r=cnt;
        }
        tree[tree[k].l].w=(mid-dl+1)*tree[k].lazy;
        tree[tree[k].r].w=(dr-mid)*tree[k].lazy;
        tree[tree[k].l].lazy=tree[tree[k].r].lazy=tree[k].lazy;
        tree[k].lazy=-1;
    }
    return ;
}
inline void update(int l,int r,int w,int &k,int dl,int dr){
    if(!k){
        cnt++;
        k=cnt;
    }
    if(dl>=l&&dr<=r){
        tree[k].w=(dr-dl+1)*w;
        tree[k].lazy=w;
        return ;
    }
    push_down(k,dl,dr);
    int mid=(dl+dr)>>1;
    if(l<=mid){
        update(l,r,w,tree[k].l,l,mid);
    }
    if(r>mid){
        update(l,r,w,tree[k].r,mid+1,r);
    }
    tree[k].w=tree[tree[k].l].w+tree[tree[k].r].w;
    return ;
}
signed main(){
    cin>>n>>q;
    for(int i=1;i<=q*log2(n);i++){
        tree[i].lazy=-1;
    }
    while(q--){
        int l,r,k;
        cin>>l>>r>>k;
        if(k==1){
            update(l,r,1,rt,1,n);
            cout<<n-tree[rt].w<<"\n";
        }else{
            update(l,r,0,rt,1,n);
            cout<<n-tree[rt].w<<"\n";
        }
    }
    return 0;
}
2024/11/12 11:47
加载中...