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

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: nagasan0210
• 提出日時: 2026-04-19 11:26:35
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 1,431 ms / 2,000 ms
• コード長: 4,785 bytes
• コンパイル時間: 3,051 ms
• コンパイル使用メモリ: 353,612 KB
• 実行使用メモリ: 32,084 KB
• 最終ジャッジ日時: 2026-04-19 11:27:27
• 合計ジャッジ時間: 29,346 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

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

ソースコード

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

#define rep(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rrep(i, a, b) for (int i = (int)(a); i > (int)(b); i--)
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define PQ priority_queue<int, vector<int>, greater<int>>
#define PQ_g priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>>
#define chmin(a, b) a = min(a, b)
#define chmax(a, b) a = max(a, b)
const int d4[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
const int d8[8][2] = {{0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}};
void Yes(bool b) {cout << (b ? "Yes" : "No") << endl;}

ll isqrt(ll n) {
    ll l = 0LL, r = (1LL << 16);
    while (r - l > 1LL) {
        ll m = (l + r) >> 1;
        if (n < m * m) r = m;
        else l = m;
    }
    return l;
}

class LazySegtree {
    private:
        //0-index
        //区間和
        vector<vector<ll>> data;
        vector<ll> data_not_0_cnt;
        //更新する数そのもの
        vector<ll> lazy_num;
        vector<ll> lazy_sqrt;
        int siz;

        void add_data(int ind1, int ind2, int ind_ret) {
            rep(i, 0, 6) data[ind_ret][i] = data[ind1][i] + data[ind2][i];
            data_not_0_cnt[ind_ret] = data_not_0_cnt[ind1] + data_not_0_cnt[ind2];
        }

        void eval(int ind, int l, int r) {
            if (lazy_num[ind] == -1LL) {
                rep(i, 0, lazy_sqrt[ind]) {
                    rep(j, 0, 5) data[ind][j] = data[ind][j + 1];
                    data[ind][5] = data_not_0_cnt[ind];
                }
                if (ind < siz) {
                    lazy_sqrt[ind << 1] =min(5LL, lazy_sqrt[ind << 1] + lazy_sqrt[ind]);
                    lazy_sqrt[(ind << 1) + 1] =min(5LL, lazy_sqrt[(ind << 1) + 1] + lazy_sqrt[ind]);
                }
            } else {
                rep(i, 0, lazy_sqrt[ind]) lazy_num[ind] = isqrt(lazy_num[ind]);
                data[ind][0] = lazy_num[ind];
                rep(j, 0, 5) data[ind][j + 1] = isqrt(data[ind][j]);
                rep(j, 0, 6) data[ind][j] *= (ll)(r - l);
                if (data[ind][0] == 0) data_not_0_cnt[ind] = 0LL;
                else data_not_0_cnt[ind] = (ll)(r - l);
                
                if (ind < siz) {
                    lazy_sqrt[ind << 1] = 0LL;
                    lazy_sqrt[(ind << 1) + 1] = 0LL;
                    lazy_num[ind << 1] = lazy_num[ind];
                    lazy_num[(ind << 1) + 1] = lazy_num[ind];
                }
            }
            
            lazy_sqrt[ind] = 0LL;
            lazy_num[ind] = -1LL;
        }

        //x == -1 then isqrt else change_num
        int sub_update(int a, int b, int ind, int l, int r, ll x) {
            eval(ind, a, b);
            if (r <= a || b <= l) return 0; //何もしない
            if (l <= a && b <= r) {
                if (x == -1LL) {
                    lazy_sqrt[ind] = min(5LL, lazy_sqrt[ind] + 1);
                } else {
                    lazy_sqrt[ind] = 0LL;
                    lazy_num[ind] = x; 
                }
                eval(ind, a, b);
                return 0;
            }
            int m = (a + b) >> 1;
            sub_update(a, m, (ind << 1), l, r, x);
            sub_update(m, b, (ind << 1) + 1, l, r, x);
            add_data((ind << 1), (ind << 1) + 1, ind);
            return 0;
        }

        ll sub_calc(int a, int b, int ind, int l, int r) {
            eval(ind, a, b);
            if (r <= a || b <= l) return 0LL; //単位元
            if (l <= a && b <= r) return data[ind][0];
            int m = (a + b) >> 1;
            //モノイドの演算
            return sub_calc(a, m, (ind << 1), l, r) + sub_calc(m, b, (ind << 1) + 1, l, r);
        }

    public:
        LazySegtree(int n) {
            siz = 1;
            while (siz < n) siz <<= 1;
            data.assign(siz << 1, vector<ll>(6, 0LL));
            data_not_0_cnt.assign(siz << 1, 0LL);
            lazy_num.assign(siz << 1, -1LL);
            lazy_sqrt.assign(siz << 1, 0LL);
        }

        //半開区間 [l, r)
        void update(int l, int r, ll x) {sub_update(0, siz, 1, l, r, x);}
        
        //半開区間 [l, r)
        ll calc(int l, int r) {return sub_calc(0, siz, 1, l, r);}
};



int main() {
    int n, q; cin >> n >> q;
    LazySegtree A(n);
    rep(i, 0, n) {
        ll a; cin >> a;
        A.update(i, i + 1, a);
    }
    rep(i, 0, q) {
        int mode, l, r; cin >> mode >> l >> r;
        if (mode == 0) {
            cout << A.calc(l, r) << endl;
        } else {
            if (mode == 1) {
                ll x; cin >> x;
                A.update(l, r, x);
            } else {
                A.update(l, r, -1LL);
            }
        }
    }
}