#1158976 (C++17) No.3507 RangeSum RangeUpdate RangeSqrt

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: GOTKAKO
• 提出日時: 2026-04-18 02:43:46
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 331 ms / 2,000 ms
• コード長: 9,928 bytes
• コンパイル時間: 1,678 ms
• コンパイル使用メモリ: 227,120 KB
• 実行使用メモリ: 21,632 KB
• 最終ジャッジ日時: 2026-04-18 02:43:55
• 合計ジャッジ時間: 8,937 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_0

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

ソースコード

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

template<typename T>
bool chmin(T &a,T b){ //a>bならa=bに更新してtrue.
    if(a > b){a = b; return true;}
    else return false;
}
template<typename T> 
bool chmax(T &a,T b){ //a<bならa=bに更新してtrue.
    if(a < b){a = b; return true;}
    else return false;
}
template<typename T> 
T safemod(T a,T m){a %= m,a += m;return a>=m?a-m:a;} //return x = a mod m. 
template<typename T> 
T floor(T a,T b){ //return a/b切り下げ.
    if(b < 0) a *= -1,b *= -1;
    return a<0?(a+1)/b-1:a/b; 
   
}
template<typename T> 
T ceil(T a,T b){ //return a/b切り上げ.
    if(b < 0) a *= -1,b *= -1;
    return a>0?(a-1)/b+1:a/b; 
}
template<typename T> 
pair<T,T> invgcd(T a,T b){
    //return {gcd(a,b),x} (xa≡g(mod b))
    a = safemod(a,b);
    if(a == 0) return {b,0};
    T x = 0,y = 1,memob = b;
    while(a){
        T q = b/a;
        b -= a*q;
        swap(x,y); y -= q*x;
        swap(a,b);
    }
    if(x < 0) x += memob/b;
    return {b,x};
}
template<typename T>
bool isABmoreC(T a,T b,T c){ //a*b=cはfalse
    if(c%b) return a>=ceil(c,b);
    else return a>ceil(c,b);
}
template<typename T>
bool isABmoreC2(T a,T b,T c){return a>=ceil(c,b);} //a*b=cはtrue.
template<typename T>
bool isABlessC(T a,T b,T c){ //a*b=cはfalse.
    if(c%b) return a<=floor(c,b);
    else return a<floor(c,b);
}
template<typename T>
bool isABlessC2(T a,T b,T c){return a<=floor(c,b);} //a*b=cはtrue.
template<typename T>
T Kthpower(T a,int k){ //return a^k オーバーフローは考慮しない.
    T ret = 1;
    while(k){
        if(k&1) ret *= a;
        a *= a; k >>= 1;
    }
    return ret;
}
template<typename T>
pair<T,bool> Kthpower2(T a,int k){ //return {a^k,オーバーした?} オーバーフローは考慮する.
    T ret = 1,maxv = numeric_limits<T>::max();
    while(k){
        if(k&1){
            if(isABmoreC(ret,a,maxv)) return {-1,true};
            ret *= a;
        }
        if(k == 1) break;
        if(isABmoreC(a,a,maxv)) return {-1,true};
        a *= a; k >>= 1;
    }
    return {ret,false};
}
template<typename T>
T Kthroot(T a,int k){ //return floor(a^(1/k));
    assert(k > 0 && a >= 0);
    if(k == 1 || a <= 1) return a;
    T ret = pow(a,1.0/k);
    while(true){
        auto [check,over] = Kthpower2(ret+1,k);
        if(over || check > a) break;
        ret++;
    }    
    while(true){
        auto [check,over] = Kthpower2(ret,k);
        if(!over && check <= a) break;
        ret--;
    }    
    return ret;
}
template<typename T>
T powmod(T a,T b,T m){//a^b(mod m)を返す.
    assert(b >= 0);
    __int128_t ret = 1,p = a;
    while(b){
        if(b&1) ret = ret*p%m;
        p = p*p%m; b >>= 1;
    }
    return T(ret);
}
template<typename T>
T divmod(T a,T b,T m){//a/b(mod m)を返す 素数mod必須.
    return (T)((__int128_t)a*powmod(b,m-2,m)%m); 
}

struct SS{
    long long len,sum,low,c,zero;
    bool fail;
};
using FF = pair<int,int>;
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){
        SS ret; ret.fail = false;
        ret.len = a.len+b.len,ret.sum = a.sum+b.sum;
        ret.low = min(a.low,b.low),ret.c = 0,ret.zero = a.zero+b.zero;
        if(a.low == ret.low) ret.c += a.c;
        if(b.low == ret.low) ret.c += b.c;
        return ret;
    }
    SS mapping(FF f, SS x){
        if(f.first == -1 && f.second == 0) return x;
        if(f.first != -1){
            if(f.first == 0) return {x.len,0,1001001001,0,x.len,false};
            else return {x.len,x.len*f.first,f.first,x.len,0,false};
        }
        if(x.len == x.c+x.zero){
            while(f.second && x.low > 1) f.second--,x.low = Kthroot(x.low,2);
            return {x.len,x.low*x.c,x.low,x.c,x.zero,false};
        }
        else return {0,0,1001001001,0,0,true};
    }
    FF composition(FF f, FF g){
        auto [f1,f2] = f;
        auto [g1,g2] = g;
        if(f1 != -1) return f;
        if(g1 == -1) return {-1,f2+g2};
        while(g1 > 1 && f2) f2--,g1 = Kthroot(g1,2);
        return {g1,0};
    }
    SS e(){return {0,0,1001001001,0,0,false};}
    FF id(){return {-1,0};}
    //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 &a : give){
        int v; cin >> v;
        if(v == 0) a = {1,0,1001001001,0,1,false};
        else a = {1,v,v,1,0,false};
    }
    SegmentTreeBeats Z(give);
    while(Q--){
        int t,l,r; cin >> t >> l >> r;
        if(t == 1){
            int x; cin >> x;
            Z.update(l,r,{x,0});
        }
        else if(t == 2) Z.update(l,r,{-1,1});
        else cout << Z.rangeans(l,r).sum << "\n";
    }
}