#1160897 (C++23) No.3507 RangeSum RangeUpdate RangeSqrt

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: こめだわら
• 提出日時: 2026-04-21 13:39:34
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 590 ms / 2,000 ms
• コード長: 3,766 bytes
• コンパイル時間: 4,553 ms
• コンパイル使用メモリ: 382,180 KB
• 実行使用メモリ: 27,136 KB
• 最終ジャッジ日時: 2026-04-21 13:39:57
• 合計ジャッジ時間: 20,646 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge2_1

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

#define rep(i,n) for(ll i=0;i<n;++i)
#define all(a) (a).begin(),(a).end()
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
template<class T> T div_floor(T a, T b) { return a / b - ((a ^ b) < 0 && a % b); }
template<class T> T div_ceil(T a, T b) { return a / b + ((a ^ b) > 0 && a % b); }
template <typename T, typename U> inline bool chmin(T &x, U y) { return (y < x) ? (x = y, true) : false; }
template <typename T, typename U> inline bool chmax(T &x, U y) { return (x < y) ? (x = y, true) : false; }

template<typename T>
ostream &operator<<(ostream &os, const vector<T> &a){
    if (a.empty()) return os;
    os << a.front();
    for (auto e : a | views::drop(1)){
        os << ' ' << e;
    }
    return os;
}

void dump(auto ...vs){
    ((cout << vs << ' '), ...) << endl;
}

#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;

ll isqrt(ll n){
    assert(n>=0);
    ll s=sqrtl(n);
    while ((s+1)*(s+1)<=n)s++;
    while (s*s>n)s--;
    return s;
}

const int Width=6;

struct S{
    ll L;
    array<ll,Width> A;
    S(){}
    S(ll _x){
        L=1;
        set(_x);
    }
    void set(ll x){
        A[0]=x*L;
        rep(i,Width-1){
            x=isqrt(x);
            A[i+1]=x*L;
        }
        return;
    };
    void shift(ll n){
        array<ll,Width> B;
        for (ll i=0;i<Width;i++){
            if (i+n<Width){
                B[i]=A[i+n];
            }
            else{
                B[i]=A[Width-1];
            }
        }
        swap(A,B);
        return;
    };
};

struct F{
    int type=0;
    ll x=0;
    ll s=0;
};

S op(S x,S y){
    S z;
    z.L=x.L+y.L;
    rep(i,Width){
        z.A[i]=x.A[i]+y.A[i];
    }
    return z;
}

S e(){
    S x(0);
    x.L=0;
    return x;
}

S mapping(F f,S x){
    if (f.type==1){
        x.set(f.x);
    }
    x.shift(f.s);
    return x;
}

F composition(F f,F g){
    if (f.type==1){
        return f;
    }
    g.s+=f.s;
    return g;
}

F id(){
    F f;
    f.type=0;
    f.x=0;
    f.s=0;
    return f;
}

bool naive=false;

void solve() {
    ll N,Q;
    cin>>N>>Q;
    vector<ll> A(N);
    rep(i,N)cin>>A[i];
    vector<S> V(N);
    rep(i,N){
        V[i]=S(A[i]);
    }
    lazy_segtree<S,op,e,F,mapping,composition,id> lst(V);
    rep(_,Q){
        ll t;
        cin>>t;
        if (t==0){
            ll l,r;
            cin>>l>>r;
            S res=lst.prod(l,r);
            ll ans=res.A[0];
            if (naive){
                ll nans=0;
                for (ll i=l;i<r;i++){
                    nans+=A[i];
                }
                if (ans!=nans){
                    dump(_,l,r);
                }
                assert(ans==nans);
            }
            cout<<ans<<'\n';
        }
        else if (t==1){
            ll l,r,x;
            cin>>l>>r>>x;
            F f;
            f.type=1;
            f.x=x;
            f.s=0;
            lst.apply(l,r,f);
            if (naive){
                for (ll i=l;i<r;i++){
                    A[i]=x;
                }
            }
        }
        else if (t==2){
            ll l,r;
            cin>>l>>r;
            F f;
            f.type=0;
            f.x=0;
            f.s=1;
            lst.apply(l,r,f);
            if (naive){
                for (ll i=l;i<r;i++){
                    A[i]=isqrt(A[i]);
                }
            }
        }
    }
    return;
}


int main() {
    cin.tie(0)->sync_with_stdio(0);
    ll T=1;
    while (T--){
        solve();
    }
    return 0;
}