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

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: nagasan0210
• 提出日時: 2026-04-19 08:58:38
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 5,630 bytes
• コンパイル時間: 2,562 ms
• コンパイル使用メモリ: 339,252 KB
• 実行使用メモリ: 27,904 KB
• 最終ジャッジ日時: 2026-04-19 08:59:10
• 合計ジャッジ時間: 28,052 ms
• ジャッジサーバーID （参考情報）: judge2_1 / judge1_1

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

ソースコード

#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;
}

typedef struct {
    //表面上の数（区間和含む）
    ll cur_num = 0LL;
    //葉にある0でない数
    ll not_0_cnt = 0LL;
    ll l_ind = 0LL, r_ind = 0LL;
    //isqrt済みの数を前計算したら、あとは線形
    //data[i] = floor(cur_num ^ (1 / 2 ^ i))
    ll data[6] = {0, 0, 0, 0, 0, 0};

    void my_isqrt() {
        for (int i = 0; i < 5; i++) data[i] = data[i + 1];
        data[5] = not_0_cnt;
        cur_num = data[0];
    }

    void update_num(ll n, ll l0, ll r0) {
        l_ind = l0;
        r_ind = r0;
        cur_num = n * (r_ind - l_ind);
        data[0] = n;
        for (int i = 0; i < 5; i++) data[i + 1] = isqrt(data[i]);
        for (int i = 0; i <= 5; i++) data[i] *= (r_ind - l_ind);

        if (cur_num == 0LL) {
            not_0_cnt = 0LL;
        } else {
            not_0_cnt = (r_ind - l_ind);
        }
    }
} Node;

Node add(Node node1, Node node2) {
    Node ret;
    ret.l_ind = node1.l_ind;
    ret.r_ind = node1.r_ind;
    ret.cur_num = node1.cur_num + node2.cur_num;
    for (int i = 0; i <= 5; i++) ret.data[i] = node1.data[i] + node2.data[i];
    ret.not_0_cnt = node1.not_0_cnt + node2.not_0_cnt;

    return ret;
}

typedef struct {
    ll isqrt_cnt = 0LL;
    ll lazy_num = -1LL;

    void update_num(ll num) {
        isqrt_cnt = 0LL;
        lazy_num = num;
    }

    void update_isqrt() {
        if (lazy_num == -1LL) {
            if (isqrt_cnt < 5) isqrt_cnt++;
        }
        else lazy_num = isqrt(lazy_num);
    }

    //(更新する数か？　そうでないときは、isqrtの数, 更新する数（区間和でない） or isqrtの数)
    pair<bool, ll> consume_lazy(){
        pair<bool, ll> ret;
        if (lazy_num == -1LL) {
            ret.first = false;
            ret.second = isqrt_cnt;
            isqrt_cnt = 0LL;
            lazy_num = -1LL;
        } else {
            ret.first = true;
            ret.second = lazy_num;
            isqrt_cnt = 0LL;
            lazy_num = -1LL;
        }
        return ret;
    }
} LazyStock;



class LazySegtree {
    private:
        int siz;
        vector<Node> data;
        vector<LazyStock> lazy;

        void eval(int ind, int l, int r) {
            pair<bool, ll> lazy_p = lazy[ind].consume_lazy();
            if (lazy_p.first) {
                data[ind].update_num(lazy_p.second, (ll)l, (ll)r);
                if (ind < siz) {
                    lazy[ind << 1].update_num(lazy_p.second);
                    lazy[(ind << 1) + 1].update_num(lazy_p.second);
                }
            } else {
                for (int i = 0; i < lazy_p.second; i++) data[ind].my_isqrt();
                if (ind < siz) {
                    for (int i = 0; i < lazy_p.second; i++) lazy[ind << 1].update_isqrt();
                    for (int i = 0; i < lazy_p.second; i++) lazy[(ind << 1) + 1].update_isqrt();
                }
            }
        }

        //x == -1ならisqrt、そうでないなら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[ind].update_num(x); 
                else lazy[ind].update_isqrt();
                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);
            data[ind] = add(data[(ind << 1)], data[(ind << 1) + 1]);
            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 0; //単位元
            if (l <= a && b <= r) return data[ind].cur_num;
            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.resize(siz << 1);
            lazy.resize(siz << 1);
        }

        //半開区間 [l, r)
        void update(int l, int r, ll x) {sub_update(0, siz, 1, l, r, x);}
        
        //半開区間 [l, r)
        int 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 {
            ll x;
            if (mode == 1) cin >> x;
            else x = -1LL;
            A.update(l, r, x);
        }
    }
}