题解：AT_abc430_g [ABC430G] Range Set Modifying Query

Aux_sky · 2026-10-23 15:55:44 · 题解

考虑珂朵莉树维护连续段。

这个插入删除一个值显然是一个珂朵莉树的板子。

对于每一种值都开一棵珂朵莉树，插入就是区间赋值 1，删除就是区间赋值 0。

我们另外再用一棵线段树来维护每个位置的 \text{size} 用来查询答案。

那么对于 assign 操作就是从 l,r 两个位置分裂，枚举中间每一个区间，在线段树上做一个区间加即可。

由于我们每次都会把枚举过的连续段都删掉，枚举总量均摊是 \mathcal O(Q) 的，带上线段树和珂朵莉本身的复杂度就是 \mathcal O(Q\log n)。

::::success[Code]

const int N=3e5+5;
int n,Q;
struct Segment{
    struct tree{int v,x;}tr[N<<2];
    int lz[N<<2];
    tree merge(tree x,tree y){
        tree res;
        if(x.v==y.v)res={x.v,x.x+y.x};
        else if(x.v>y.v)res=x;
        else res=y;
        return res; 
    }
    void Add(int x,int v){
        lz[x]+=v;
        tr[x].v+=v;
    }
    void push(int x){
        Add(x<<1,lz[x]);
        Add(x<<1|1,lz[x]);
        lz[x]=0;
    }
    void add(int l,int r,int x,int L,int R,int v){
        if(l!=r)push(x);
        if(l>=L&&r<=R){
            Add(x,v);
            return;
        }
        int mid((l+r)>>1);
        if(mid>=L)add(l,mid,x<<1,L,R,v);
        if(mid<R)add(mid+1,r,x<<1|1,L,R,v);
        tr[x]=merge(tr[x<<1],tr[x<<1|1]);
    }
    void bd(int l,int r,int x){
        if(l==r){
            tr[x]={0,1};
            return;
        }
        int mid((l+r)>>1);
        bd(l,mid,x<<1);
        bd(mid+1,r,x<<1|1);
        tr[x]=merge(tr[x<<1],tr[x<<1|1]);
    }
    tree query(int l,int r,int x,int L,int R){
        if(l!=r)push(x);
        if(l>=L&&r<=R)return tr[x];
        int mid((l+r)>>1);
        if(mid<L)return query(mid+1,r,x<<1|1,L,R);
        if(mid>=R)return query(l,mid,x<<1,L,R);
        return merge(query(l,mid,x<<1,L,R),query(mid+1,r,x<<1|1,L,R));
    }
}T;
struct ODT{
    struct node{
        int l,r,v;
        bool operator <(const node B)const{return l<B.l;}
    };
    set<node>s; 
    auto split(int x){
        auto it=s.lower_bound({x,0,0});
        if(it==s.begin()||it->l==x)return it;
        --it;
        int l=it->l,r=it->r,v=it->v;
        s.erase(it);
        s.insert({l,x-1,v});
        return s.insert({x,r,v}).first;
    }
    void assign(int l,int r,int v){
        auto ed=split(r+1),st=split(l);
        for(auto it=st;it!=ed;++it){
            int l=it->l,r=it->r,v=it->v;
            T.add(1,n,1,l,r,-v);
        }
        s.erase(st,ed);
        s.insert({l,r,v});
        T.add(1,n,1,l,r,v);
    }
}odt[65];
int main(){
    scanf("%d%d",&n,&Q);
    T.bd(1,n,1);
    for(int i=1;i<=60;++i)odt[i].s.insert({1,n,0});
    while(Q--){
        int opt,l,r;
        scanf("%d%d%d",&opt,&l,&r);
        if(opt==1){
            int x;
            scanf("%d",&x);
            odt[x].assign(l,r,1);
        }
        if(opt==2){
            int x;
            scanf("%d",&x);
            odt[x].assign(l,r,0);
        }
        if(opt==3){
            auto ans=T.query(1,n,1,l,r);
            printf("%d %d\n",ans.v,ans.x);
        }
    }
    return 0;
}

::::