#1182856 (C++23) No.3671 Reusable Lazy Segment Tree

• 問題: No.3671 Reusable Lazy Segment Tree
• ユーザー: あいすあうと
• 提出日時: 2026-09-05 01:32:24
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 4,979 ms / 6,000 ms
• コード長: 12,025 bytes
• コンパイル時間: 5,406 ms
• コンパイル使用メモリ: 393,932 KB
• 実行使用メモリ: 33,960 KB
• 最終ジャッジ日時: 2026-09-05 01:33:08
• 合計ジャッジ時間: 39,025 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 19

ソースコード

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
using i128=__int128;
using P=pair<ll,ll>;
template<typename T> using vc=vector<T>;
template<typename T> using vv=vc<vc<T>>;
using vl=vc<ll>;
using vvl=vc<vc<ll>>;
using vul=vc<ull>;
using vs=vc<string>;
using vb=vc<bool>;
#define rep(i,s,n) for(ll i=s;i<(n);i++)
#define Rep(i,s,n) for(ll i=n;i>=s;i--)
#define nall(x) x.begin(),x.end()
#define rall(a) a.rbegin(),a.rend()
#define pb push_back
#define eb emplace_back
#define pob pop_back
#define nexp(v) next_permutation(v)
#define prep(v) prev_permutation(v)
#define YES cout<<"Yes"<<endl
#define NO cout<<"No"<<endl
#define YN {cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#define M1 cout<<"-1"<<endl
const long long INF=(1LL<<62)-(1LL<<31)-1;
#define endl '\n'
using mint=modint998244353;
using mint7=modint1000000007;
//vl dx={1,-1,0,0};vl dy={0,0,1,-1};
//vl dx={0,0,1,1,1,-1,-1,-1};vl dy={1,-1,0,1,-1,0,1,-1};
bool out_grid(ll i, ll j, ll h, ll w){return (!(0<=i && i<h && 0<=j && j<w));}
void chmin(ll &a,ll b){if(a>b)a=b;}
void chmax(ll &a,ll b){if(a<b)a=b;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll ceil_div(ll a,ll b){return (a+(b-1))/b;}

template<typename Node>
struct PersistentRBSTBase{
    using Ptr=Node*;

    static constexpr size_t BLOCK=1<<14;
    vc<unique_ptr<Node[]>> pool;
    size_t used=0;

    template<typename...Args>
    Ptr my_new(Args&&...args){
        size_t b=used/BLOCK,o=used%BLOCK;
        if(b==pool.size())pool.eb(make_unique<Node[]>(BLOCK));
        Ptr p=&pool[b][o];
        *p=Node(forward<Args>(args)...);
        ++used;
        return p;
    }

    size_t checkpoint()const{return used;}

    void rollback(size_t p){
        assert(p<=used);
        used=p;
    }

    Ptr make_tree()const{return nullptr;}
    int size(Ptr t)const{return count(t);}

    Ptr merge(Ptr l,Ptr r){
        if(!l||!r)return l?l:r;
        if((uint64_t)rng()*(l->cnt+r->cnt)>>32<(uint32_t)l->cnt){
            Ptr t=clone(l);
            push(t);
            t->r=merge(t->r,r);
            return update(t);
        }else{
            Ptr t=clone(r);
            push(t);
            t->l=merge(l,t->l);
            return update(t);
        }
    }

    pair<Ptr,Ptr> split(Ptr t,int k){
        assert(0<=k&&k<=count(t));
        if(!t)return {nullptr,nullptr};
        Ptr u=clone(t);
        push(u);
        if(k<=count(u->l)){
            auto [a,b]=split(u->l,k);
            u->l=b;
            return {a,update(u)};
        }else{
            auto [a,b]=split(u->r,k-count(u->l)-1);
            u->r=a;
            return {update(u),b};
        }
    }

    Ptr build(int l,int r,const vc<decltype(Node::key)>&v){
        if(l==r)return nullptr;
        int m=(l+r)>>1;
        Ptr t=my_new(v[m]);
        t->l=build(l,m,v);
        t->r=build(m+1,r,v);
        return update(t);
    }

    Ptr build(const vc<decltype(Node::key)>&v){
        return build(0,(int)v.size(),v);
    }

    template<typename...Args>
    Ptr insert(Ptr t,int k,Args&&...args){
        assert(0<=k&&k<=count(t));
        auto [a,b]=split(t,k);
        return merge(merge(a,my_new(forward<Args>(args)...)),b);
    }

    Ptr erase(Ptr t,int k){
        assert(0<=k&&k<count(t));
        auto [a,b]=split(t,k);
        auto [c,d]=split(b,1);
        return merge(a,d);
    }

protected:
    static uint32_t rng(){
        static uint64_t x=88172645463325252ULL;
        x^=x<<7;
        x^=x>>9;
        return (uint32_t)x;
    }

    int count(Ptr t)const{return t?t->cnt:0;}
    Ptr clone(Ptr t){return t?my_new(*t):nullptr;}
    virtual void push(Ptr)=0;
    virtual Ptr update(Ptr)=0;
};

template<typename S,typename F>
struct PersistentLazyReversibleRBSTNode{
    using Self=PersistentLazyReversibleRBSTNode<S,F>;
    Self*l=nullptr,*r=nullptr;
    S key,sum;
    F lazy;
    int cnt=1;
    bool rev=false;

    PersistentLazyReversibleRBSTNode(const S&x=S(),const F&f=F()):key(x),sum(x),lazy(f){}
};

template<
    typename S,
    typename F,
    S(*op)(S,S),
    S(*mapping)(S,F),
    F(*composition)(F,F),
    S(*ts)(S)
>
struct PersistentLazyReversibleRBST:PersistentRBSTBase<PersistentLazyReversibleRBSTNode<S,F>>{
    using Node=PersistentLazyReversibleRBSTNode<S,F>;
    using Base=PersistentRBSTBase<Node>;
    using Ptr=typename Base::Ptr;

    using Base::build;
    using Base::checkpoint;
    using Base::clone;
    using Base::count;
    using Base::erase;
    using Base::insert;
    using Base::merge;
    using Base::rollback;
    using Base::size;
    using Base::split;

    S fold(Ptr t,int l,int r)const{
        assert(0<=l&&l<=r&&r<=count(t));
        return fold_impl(t,l,r,F(),false);
    }

    S get(Ptr t,int k)const{
        assert(0<=k&&k<count(t));
        return fold(t,k,k+1);
    }

    S all_fold(Ptr t)const{
        return t?t->sum:S();
    }

    Ptr reverse(Ptr t,int l,int r){
        assert(0<=l&&l<=r&&r<=count(t));
        if(l==r)return t;
        auto [a,b]=split(t,l);
        auto [c,d]=split(b,r-l);
        toggle(c);
        return merge(a,merge(c,d));
    }

    Ptr apply(Ptr t,int l,int r,const F&f){
        assert(0<=l&&l<=r&&r<=count(t));
        if(l==r||f==F())return t;
        return apply_impl(t,l,r,f);
    }

    Ptr set(Ptr t,int k,const S&x){
        assert(0<=k&&k<count(t));
        auto [a,b]=split(t,k);
        auto [c,d]=split(b,1);
        return merge(a,merge(this->my_new(x),d));
    }

protected:
    S sum(Ptr t)const{return t?t->sum:S();}

    void toggle(Ptr t){
        if(!t)return;
        swap(t->l,t->r);
        t->sum=ts(t->sum);
        t->rev^=1;
    }

    void propagate(Ptr t,const F&f){
        if(!t||f==F())return;
        t->lazy=composition(t->lazy,f);
        t->key=mapping(t->key,f);
        t->sum=mapping(t->sum,f);
    }

    void push(Ptr t)override{
        if(!t||(!t->rev&&t->lazy==F()))return;
        if(t->l)t->l=clone(t->l);
        if(t->r)t->r=clone(t->r);
        if(t->rev){
            toggle(t->l);
            toggle(t->r);
            t->rev=false;
        }
        if(t->lazy!=F()){
            propagate(t->l,t->lazy);
            propagate(t->r,t->lazy);
            t->lazy=F();
        }
    }

    Ptr update(Ptr t)override{
        push(t);
        t->cnt=1;
        t->sum=t->key;
        if(t->l){
            t->cnt+=t->l->cnt;
            t->sum=op(t->l->sum,t->sum);
        }
        if(t->r){
            t->cnt+=t->r->cnt;
            t->sum=op(t->sum,t->r->sum);
        }
        return t;
    }

    Ptr apply_impl(Ptr t,int l,int r,const F&f){
        if(!t||l==r)return t;

        if(l==0&&r==count(t)){
            Ptr u=clone(t);
            propagate(u,f);
            return u;
        }

        Ptr u=clone(t);
        push(u);

        int ls=count(u->l);

        if(l<ls){
            u->l=apply_impl(
                u->l,
                l,
                min(r,ls),
                f
            );
        }

        if(l<=ls&&ls<r){
            u->key=mapping(u->key,f);
        }

        if(ls+1<r){
            u->r=apply_impl(
                u->r,
                max(0,l-ls-1),
                r-ls-1,
                f
            );
        }

        return update(u);
    }

    S fold_impl(Ptr t,int l,int r,const F&anc_lazy,bool anc_rev)const{
        if(!t||l==r)return S();

        int n=count(t);

        if(l==0&&r==n){
            S res=anc_rev?ts(t->sum):t->sum;
            return mapping(res,anc_lazy);
        }

        Ptr left=anc_rev?t->r:t->l;
        Ptr right=anc_rev?t->l:t->r;
        int ls=count(left);

        F child_lazy=composition(t->lazy,anc_lazy);
        bool child_rev=t->rev^anc_rev;

        S res=S();
        bool has=false;

        auto add=[&](const S&x){
            if(has)res=op(res,x);
            else res=x,has=true;
        };

        if(l<ls){
            add(fold_impl(
                left,
                l,
                min(r,ls),
                child_lazy,
                child_rev
            ));
        }

        if(l<=ls&&ls<r){
            add(mapping(t->key,anc_lazy));
        }

        if(ls+1<r){
            add(fold_impl(
                right,
                max(0,l-ls-1),
                r-ls-1,
                child_lazy,
                child_rev
            ));
        }

        return has?res:S();
    }
};

constexpr uint32_t mask=(1u<<30)-1;

struct F{
    uint32_t keep,set;

    F(uint32_t keep_=mask,uint32_t set_=0):keep(keep_),set(set_){}

    friend bool operator==(const F&a,const F&b){
        return a.keep==b.keep&&a.set==b.set;
    }

    friend bool operator!=(const F&a,const F&b){
        return !(a==b);
    }
};

struct S{
    array<uint32_t,17> cnt{};
    uint32_t sum=0;
    int len=0;

    S()=default;

    S(uint32_t x,int len_):sum(x&mask),len(len_){
        if(len==1)cnt[0]=x&mask;
    }
};

S op(S a,S b){
    S res;

    res.len=a.len+b.len;
    res.sum=(a.sum+b.sum)&mask;

    uint32_t carry=0;

    rep(k,0,17){
        uint32_t x=a.cnt[k];
        uint32_t y=b.cnt[k];
        uint32_t z=x^y;

        res.cnt[k]=z^carry;
        carry=(x&y)|(carry&z);
    }

    return res;
}

S mapping(S x,F f){
    if(x.len==0||f==F())return x;

    uint32_t affected=mask^f.keep;
    uint64_t old=0;

    rep(k,0,17){
        old+=(uint64_t)(x.cnt[k]&affected)<<k;

        x.cnt[k]=
            (x.cnt[k]&f.keep)|
            (((x.len>>k)&1)?f.set:0);
    }

    uint64_t nw=(uint64_t)x.len*f.set;

    x.sum=(uint32_t)(
        (uint64_t)x.sum+nw-old
    )&mask;

    return x;
}

F composition(F f,F g){
    return {
        f.keep&g.keep,
        (f.set&g.keep)|g.set
    };
}
S ts(S x){return x;}

using RBST=PersistentLazyReversibleRBST<S,F,op,mapping,composition,ts>;
RBST rbst;
RBST::Ptr root=nullptr;

uint32_t mapped_sum(const S&s,const F&f){
    if(f==F())return s.sum;

    uint32_t affected=mask^f.keep;
    uint64_t old=0;

    rep(k,0,17){
        old+=(uint64_t)(s.cnt[k]&affected)<<k;
    }

    return (uint32_t)(
        (uint64_t)s.sum+
        (uint64_t)s.len*f.set-
        old
    )&mask;
}

uint32_t fold_sum(RBST::Ptr t,int l,int r,const F&anc=F()){
    if(!t||l==r)return 0;

    if(l==0&&r==t->cnt){
        return mapped_sum(t->sum,anc);
    }

    int ls=t->l?t->l->cnt:0;

    F child=composition(t->lazy,anc);

    uint32_t res=0;

    if(l<ls){
        res+=fold_sum(
            t->l,
            l,
            min(r,ls),
            child
        );
        res&=mask;
    }

    if(l<=ls&&ls<r){
        res+=mapped_sum(t->key,anc);
        res&=mask;
    }

    if(ls+1<r){
        res+=fold_sum(
            t->r,
            max(0,l-ls-1),
            r-ls-1,
            child
        );
        res&=mask;
    }

    return res;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n,m,Q,q;
    cin >> n >> m;
    vc<uint32_t> a(n);
    rep(i,0,n)cin >> a[i];
    vc<int> l(m),r(m),L(m),R(m);
    vc<uint32_t> x(m);
    rep(i,0,m)cin >> l[i];
    rep(i,0,m)cin >> r[i];
    rep(i,0,m)cin >> x[i];
    rep(i,0,m)cin >> L[i];
    rep(i,0,m)cin >> R[i];
    vc<S> init;
    rep(i,0,n)init.eb(a[i],1);
    root=rbst.build(init);
    auto base=root;
    uint32_t cp=rbst.checkpoint();
    auto clp=[&](uint32_t p,uint32_t y)->int{
        uint32_t v=p^y;
        if(v<1)return 1;
        else if(v>(uint32_t)n)return n;
        else return (int)v;
    };
    cin >> Q;
    rep(i,1,Q+1){
        int s;
        cin >> s >> q;
        root=base;
        uint32_t y=i;
        rep(j,1,q+1){
            int z=(s+j)%m;
            int u=clp(l[z],y),v=clp(r[z],y),U=clp(L[z],y),V=clp(R[z],y);
            int lp=min(u,v),rp=max(u,v),Lp=min(U,V),Rp=max(U,V);
            uint32_t c=(x[z]^y)&mask;
            if((z+1)%2==0)root=rbst.apply(root,lp-1,rp,F(mask^c,c));
            else root=rbst.apply(root,lp-1,rp,F(c,0));
            y=fold_sum(root,Lp-1,Rp);
        }
        cout << y << endl;
        rbst.rollback(cp);
    }
}