#1131480 (C++17) No.880 Yet Another Segment Tree Problem

• 問題: No.880 Yet Another Segment Tree Problem
• ユーザー: GOTKAKO
• 提出日時: 2025-11-06 18:00:48
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 599 ms / 5,000 ms
• コード長: 7,203 bytes
• コンパイル時間: 5,018 ms
• コンパイル使用メモリ: 208,628 KB
• 実行使用メモリ: 25,148 KB
• 最終ジャッジ日時: 2025-11-06 18:08:26
• 合計ジャッジ時間: 24,200 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct SS{
    long long len,s,v,c,o,l;
    bool fail;
};
using FF = pair<long long,long long>;
class SegmentTreeBeats{
    //遅延セグ木ではmapping f,xが上手くいかない場合がある.
    //その時再帰的にやるのがBeats! 失敗回数が抑えられたら良い.
    private:
    vector<SS> dat;
    vector<FF> lazy;
    public:
    int siz = -1,n = -1,log = 0;
 
    SS op(SS a,SS b){
        if(a.len == 0) return b;
        if(b.len == 0) return a;
        SS ret; ret.len = a.len+b.len,ret.s = a.s+b.s,ret.o = a.o+b.o;
        ret.l = min(1001001001LL,a.l*b.l/gcd(a.l,b.l)),ret.fail = false;
        ret.v = max(a.v,b.v),ret.c = 0;
        if(ret.v == a.v) ret.c += a.c;
        if(ret.v == b.v) ret.c += b.c;
        return ret;
    }
    SS mapping(FF f, SS x){
        auto [fg,fv] = f;
        if(fv != -1) return {x.len,fv*x.len,fv,fv==1?0:x.len,fv==1?x.len:0,fv};
        if(fg%x.l == 0) return x;
        if(x.o+x.c == x.len){
            x.s -= x.v*x.c;
            x.v = gcd(x.v,fg);
            x.s += x.v*x.c,x.l = x.v;
            if(x.v == 1) x.c = 0,x.o = x.len;
            return x;
        }
        return {0,0,0,0,0,0,true};
    }
    FF composition(FF f, FF g){
        auto [fg,fv] = f;
        auto [gg,gv] = g;
        if(fv != -1) return f;
        if(gv != -1) return {0,gcd(fg,gv)};
        return {gcd(fg,gg),-1};
    }
    SS e(){return {0,0,0,0,0,0,false};}
    FF id(){return {0,-1};}
    //op区間演算 mapping lazy→data composition lazy→lazy
    //e 単位元 id map(id,a)=a
 
    SegmentTreeBeats(int N){init(N);}
    SegmentTreeBeats(const vector<SS> &A){//配列サイズに合わせる.
        siz = 1; n = A.size(); log = 0;
        while(siz < n) siz <<= 1,log++;
        dat.resize(siz*2,e());
        lazy.resize(siz,id());
        for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
        for(int i=siz-1; i>0; i--) merge(i);
    }
    void init(int N){ //単位元になる.
        siz = 1; n = N; log = 0;
        while(siz < n) siz *= 2,log++;
        dat.assign(siz*2,e());
        lazy.assign(siz,id());
    }
    void init(const vector<SS> &A){ //配列サイズに合わせる.
        siz = 1; n = A.size(); log = 0;
        while(siz < n) siz <<= 1,log++;
        dat.resize(siz*2,e());
        lazy.assign(siz,id());
        for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
        for(int i=siz-1; i>0; i--) merge(i);
    }
 
    private:
    void eval(int u,FF f){
        //u番目にfを適用したあと保留.
        if(u == 0) return;
        dat.at(u) = mapping(f,dat.at(u));
        if(u < siz){
            lazy.at(u) = composition(f,lazy.at(u));
            if(dat.at(u).fail) spread(u),merge(u);
            //遅延セグ木との差異はここだけ.
            //failの回数が抑えられていればok.
        } 
    }
    void spread(int u){ //uにあるFF保留を伝播.
        if(u == 0 || id() == lazy.at(u)) return;
        eval(2*u,lazy.at(u));
        eval(2*u+1,lazy.at(u));
        lazy.at(u) = id();
    }
    void merge(int u){dat.at(u) = op(dat.at(u*2),dat.at(u*2+1));} //子2つからマージ.
    public:
    void set(int pos,SS x){ //1点変更.
        assert(0 <= pos && pos < n);
        pos += siz;
        for(int i=log; i>0; i--) spread(pos>>i);
        dat.at(pos) = x;
        while(pos > 1) pos >>= 1,merge(pos); 
    }
    void update(int pos,FF f){ //1点更新 変数抜かして区間更新になってないか注意!.
        assert(0 <= pos && pos < n);
        pos += siz;
        for(int i=log; i>0; i--) spread(pos>>i);
        dat.at(pos) = mapping(f,dat.at(pos));
        while(pos > 1) pos >>= 1,merge(pos);
    }
    void update(int l,int r,FF f){ //区間更新.
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return;
        l += siz; r += siz;
        for(int i=log; i>0; i--){
            if(((l>>i)<<i) != l) spread(l>>i);
            if(((r>>i)<<i) != r) spread((r-1)>>i); 
        }
        int memoL = l,memoR = r;
        while(l < r){
            if(l&1) eval(l++,f);
            if(r&1) eval(--r,f);
            l >>= 1; r >>= 1;
        }
        l = memoL,r = memoR;
        while((l&1) == 0) l >>= 1;
        while((r&1) == 0) r >>= 1;
        r--; //-1注意.
        while(l > 1) l >>= 1,merge(l);
        while(r > 1) r >>= 1,merge(r); 
    }
 
    SS get(int pos){ //1点取得.
        assert(0 <= pos && pos < n);
        pos += siz;
        for(int i=log; i>0; i--) spread(pos>>i);
        return dat.at(pos);
    }
    SS rangeans(int l,int r){ //区間取得.
        assert(0 <= l && l <= r && r <= n);
        if(l == r) return e();
        l += siz; r += siz;
        for(int i=log; i>0; i--){
            if(((l>>i)<<i) != l) spread(l>>i);
            if(((r>>i)<<i) != r) spread((r-1)>>i); 
        }
 
        SS retl = e(),retr = e();
        while(l < r){
            if(l&1) retl = op(retl,dat.at(l++));
            if(r&1) retr = op(dat.at(--r),retr);
            l >>= 1; r >>= 1;
        }
        return op(retl,retr);
    }
    SS allrange(){return dat.at(1);} //全体取得.
 
    int maxright(const function<bool(SS)> f,int l = 0){
        assert(0 <= l && l <= n && f(e()));
        if(l == n) return n;
        l += siz;
        for(int i=log; i>0; i--) spread(l>>i);
        SS now = e();
        do{
            while(l%2 == 0) l >>= 1;
            SS next = op(now,dat.at(l));
            if(f(next) == false){
                while(l < siz){
                    spread(l); l <<= 1;
                    next = op(now,dat.at(l));
                    if(f(next)) now = next,l++;
                }
                return l-siz;
            }
            now = next; l++;
        }while((l&-l) != l);
        return n;
    }
    int minleft(const function<bool(SS)> f,int r = -1){
        if(r == -1) r = n;
        assert(0 <= r && r <= n && f(e()));
        if(r == 0) return 0;
        r += siz;
        for(int i=log; i>0; i--) spread((r-1)>>i);
        SS now = e();
        do{
            r--;
            while(r&1) r >>= 1;
            if(r == 0) r = 1;
            SS next = op(dat.at(r),now);
            if(f(next) == false){
                while(r < siz){
                    spread(r);
                    r <<= 1; r++;
                    next = op(now,dat.at(r));
                    if(f(next)) now = next,r--;
                }
                return r+1-siz;
            }
            now = next;
        }while((r&-r) != r);
        return 0;
    }
};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N,Q; cin >> N >> Q;
    vector<SS> give(N);
    for(auto &g : give){
        cin >> g.v,g.s = g.v,g.len = 1,g.c = 1,g.l = g.v,g.fail = false;
        if(g.v == 1) g.c = 0,g.o = 1;
        else g.o = 0;
    }

    SegmentTreeBeats Z(give);
    while(Q--){
        int t,l,r; cin >> t >> l >> r,l--;
        if(t <= 2){
            int x; cin >> x;
            if(t == 2) Z.update(l,r,{x,-1});
            else Z.update(l,r,{0,x});
        }
        else{
            SS now = Z.rangeans(l,r);
            if(t == 3) cout << now.v << "\n";
            else cout << now.s << "\n";
        }
    }
}