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

提出ソース
結果

問題	No.3507 RangeSum RangeUpdate RangeSqrt
コンテスト
ユーザー	n_bitand_n_per_3
提出日時	2026-03-06 01:20:46
言語	C++23 (gcc 15.2.0 + boost 1.89.0) コンパイル: `g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	WA (最新) AC (最初)
実行時間	-
コード長	12,131 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	5,184 ms
コンパイル使用メモリ	300,084 KB
実行使用メモリ	32,768 KB
最終ジャッジ日時	2026-04-17 19:31:57
合計ジャッジ時間	25,352 ms
ジャッジサーバーID （参考情報）	judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 1
other	AC * 2 WA * 27
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <functional>
#include <cassert>
#include <bit>
#include <array>
#include <atcoder/all>

using namespace std;
using namespace atcoder;
using mint = modint998244353;

#define ll long long
#define LL __int128
#define MOD 998244353
#define ld long double
#define INF 2251799813685248
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define reps(i, l, r) for(ll i = (l); i < (r); ++i)
#define foreach(c, A) for(auto c:(A))
#define vall(A) (A).begin(),(A).end()
#define vrall(A) (A).rbegin(),(A).rend()
#define slice(A, l, r) next((A).begin(), (l)), next((A).begin(), (r))
#define vin(A) for (ll iiii = 0, szszszsz = (A).size(); iiii < szszszsz; iiii++){cin >> (A)[iiii];}
#define vout(A) for (ll iiii = 0, szszszsz = (A).size(); iiii < szszszsz; iiii++){cout << (A)[iiii] << " \n"[iiii == szszszsz-1];}
#define vin2d(A) for (ll iiii = 0; iiii < (A).size(); iiii++){for (ll jjjj = 0; jjjj < (A)[iiii].size(); jjjj++){cin >> (A)[iiii][jjjj];}}
#define vout2d(A) for (ll iiii = 0; iiii < (A).size(); iiii++){for (ll jjjj = 0; jjjj < (A)[iiii].size(); jjjj++){cout << (A)[iiii][jjjj] << " \n"[jjjj==(A)[iiii].size()-1];}}
#define encode(i,j) (((i))<<32)+(j)
#define decode(v,w) ((w) ? (v)%4294967296 : (v)>>32)
#define vinc(A) for (auto &vvvv : (A)){vvvv++;}
#define vdec(A) for (auto &vvvv : (A)){vvvv--;}
#define graphin0(C, M) int aaaa,bbbb;for (int iiii = 0; iiii < (M); iiii++){cin >> aaaa >> bbbb; (C)[aaaa].push_back(bbbb); (C)[bbbb].push_back(aaaa);}
#define graphin1(C, M) int aaaa,bbbb;for (int iiii = 0; iiii < (M); iiii++){cin >> aaaa >> bbbb; (C)[aaaa-1].push_back(bbbb-1); (C)[bbbb-1].push_back(aaaa-1);}
#define lsegtype(name) name::S, name::F
#define lsegarg(name) name::op, name::e,name::comp, name::mapping, name::id

vector<ll> pow2ll{1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,2305843009213693952,4611686018427387904};
vector<ll> pow10ll{1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000,100000000000,1000000000000,10000000000000,100000000000000,1000000000000000,10000000000000000,100000000000000000,1000000000000000000};
vector<ll> di{0,1,0,-1};
vector<ll> dj{1,0,-1,0};

istream &operator>>(istream &is, mint &i){long long t; is >> t; i = t; return is; }
ostream &operator<<(ostream &os, const mint &i){ os << i.val(); return os;}

template <typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template <typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }

unsigned int bit_length(ll n){ return n > 0 ? 64 - __builtin_clzll(n) : 0;}

template <typename T>
T sum(vector<T> A){
    T res = 0;
    for (size_t i=0;i<A.size();i++){
        res += A[i];
    }
    return res;
}

ll powll(ll a, ll n, ll m){
    if (n == 0){return 1;}
    if (n == 1){return a % m;}
    LL ans = 1;
    LL p = a;
    while(n > 0){
        if ((n & 1) == 1){
            ans *= p;
            ans %= m;
        }
        n >>= 1;
        p *= p;
        p %= m;
    }
    return (ll)ans;
}

// =====================================================

template <typename info, typename func>
struct LazySegmentTree{

    vector<info> data;
    vector<func> lazy; 
    function<info(info,info)> op;
    function<info()> e;
    function<func(func,func)> composition;
    function<info(func,info)> mapping;
    function<func()> id;
    size_t sz;
    int N;
    int logN;


    LazySegmentTree(vector<info> array,
            function<info(info,info)> op,
            function<info()> e,
            function<func(func,func)> composition,
            function<info(func,info)> mapping,
            function<func()> id) 
            : op(op), e(e), composition(composition), mapping(mapping), id(id), sz(array.size()) {
                logN = bit_length(sz-1);
                N = 1 << logN;
                data.assign(2*N, e());
                lazy.assign(2*N, id());

                for (int i = 0;i<sz;i++){
                    this->data[i+N] = array[i];
                }
                for (int i = N - 1; i > 0; i--){
                    this->data[i] = op(this->data[2*i],this->data[2*i+1]);
                }
            }

            info get(int i){
                assert(0 <= i && i <= sz);
                int ii= i + N;
                line_propagate(i);
                return data[ii];
            }

            info prod(int l,int r){
                assert(0 <= l && l <= r && r <= sz);
                line_propagate(l);
                line_propagate(r);
                info resL = e();
                info resR = e();
                int li = l + N;
                int ri = r + N;
                while (li < ri){
                    if (li&1){ // 必ず奇数ノードしか取らない
                        resL = op(resL, data[li]);
                        li += 1;
                    }
                    if (ri&1){ // 必ず偶数ノードしか取らない
                        ri -= 1;
                        resR = op(data[ri], resR);
                    }
                    li >>= 1;
                    ri >>= 1;
                }
                return op(resL, resR);
            }

            void apply(int l,int r, func f){
                assert(0 <= l && l <= r && r <= sz);
                // 必要な遅延の解消
                line_propagate(l);
                line_propagate(r);

                // 遅延情報の書き込み
                int li = l + N;
                int ri = r + N;
                while (li < ri){
                    if (li&1){ // 必ず奇数ノードしか取らない
                        data[li] = mapping(f,data[li]);
                        lazy[li] = composition(f,lazy[li]);
                        li += 1;
                    }
                    if (ri&1){ // 必ず偶数ノードしか取らない
                        ri -= 1;
                        data[ri] = mapping(f,data[ri]);
                        lazy[ri] = composition(f,lazy[ri]);
                    }
                    li >>= 1;
                    ri >>= 1;
                }


                // 変更箇所の更新
                li = l + N;
                ri = r + N;
                li /= li&(-li);
                ri /= ri&(-ri);
                while (li > 1){
                    data[li>>1] = op(data[li&(-2)],data[li|1]);
                    li >>= 1;
                }
                while (ri > 1){
                    data[ri>>1] = op(data[ri&(-2)],data[ri|1]);
                    ri >>= 1;
                }
            }


            void point_propagate(int i){ // i番目のノードの遅延情報を 2*i, 2*i+1 番目のノードに伝える
                lazy[2*i] = composition(lazy[i],lazy[2*i]);
                lazy[2*i+1] = composition(lazy[i],lazy[2*i+1]);
                data[2*i] = mapping(lazy[i],data[2*i]);
                data[2*i+1] = mapping(lazy[i],data[2*i+1]);
                lazy[i] = id();
            }

            void line_propagate(int ind){ // index i のノード以上の部分の遅延を解消する
                if (ind != sz){
                    ind += N;
                    for (int i=logN;i>0;i--){
                        point_propagate(ind>>i);
                    }
                }
            }

            void all_propagate(){ // 全ての遅延を解消する
                for (int i = 1;i<N;i++){
                    point_propagate(i);
                }
            }

};



// ======================================================


// RUQ + RSQ + RIQ on ll
namespace RSQ_RUQ_RIQ{
    unsigned long long isqrt_aux(int c,unsigned long long n){
        if (c == 0){
            return 1;
        } else {
            int k = (c - 1) / 2;
            unsigned long long a = isqrt_aux(c / 2, n >> (2*k + 2));
            return (a << k) + (n >> (k+2)) / a;
        }
    }

    unsigned long isqrt(unsigned long long n){
        if (n == 0){
            return 0;
        } else {
            unsigned long long a = isqrt_aux(( 63 - __builtin_clzll(n)) / 2, n);
            return n <= a * a - 1 ? a - 1 : a;
        }
    }

    struct S
    {
        array<ll,5> values;
        ll length;
        ll zero;
    };

    struct F{
        ll num;
        ll shift;
    };

    S op(S a,S b){
        array<ll,5> res;
        for(int i = 0;i<5;i++){
            res[i] = a.values[i] + b.values[i];
        }
        return {res, a.length + b.length, a.zero + b.zero};
    }

    F comp(F f, F g){  // f○gを返す
        if (f.num != -1){
            return {f.num,f.shift};
        } else {
            return {g.num,f.shift + g.shift};
        }
    }

    S mapping(F f, S x){
        array<ll,5> res;
        if (f.num == -1){
            rep(i,5){res[i] = x.length - x.zero;}
            ll tmp = f.num;
            for(int i = 0;i<4;i++){
                if (i-f.shift >= 0){
                    res[i-f.shift] = x.values[i];
                }
            }
            return {res, x.length, x.zero};
        } else if (f.num == 0) {
            rep(i,5){res[i] = 0;}
            return {res, x.length, x.length};
        } else {
            rep(i,5){res[i] = x.length;}
            ll tmp = f.num;
            for(int i = 0;i<4;i++){
                if (i-f.shift >= 0){
                    res[i-f.shift] = tmp*x.length;
                }
                tmp = isqrt(tmp);
            }
            return {res, x.length, 0};
        }
    }

    S e(){
        array<ll,5> res;
        rep(i,5){res[i] = 0;}
        return {res,0,0};
    }

    F id(){
        return {-1,0};
    }

    S gen(ll x){
        int cz;
        array<ll,5> res;
        if (x == 0){
            cz = 1;
        } else {
            cz = 0;
        }
        res[0] = x;
        for(int i = 0;i<4;i++){
            res[i+1] = isqrt(res[i]);
        }
        return {res,1,cz};
    }
}


// ===============================================================================

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    ll N,Q;
    cin >> N >> Q;

    vector<RSQ_RUQ_RIQ::S> vec(N);
    ll tmp;
    rep(i,N){
        cin >> tmp;
        vec[i] = RSQ_RUQ_RIQ::gen(tmp);
    }
    LazySegmentTree<lsegtype(RSQ_RUQ_RIQ)> LST(vec, lsegarg(RSQ_RUQ_RIQ));

    ll t,l,r,x;
    rep(i,Q){
        cin >> t;
        if (t == 0){ // range sum
            cin >> l >> r;
            cout << LST.prod(l,r).values[0] << "\n";
        } else if (t == 1){ // range update
            cin >> l >> r >> x;
            LST.apply(l,r,{x,0});
        } else {  // range isqrt
            cin >> l >> r;
            LST.apply(l,r,{-1,1});
        }
    }
}

/*
input

8 25
0 1 2 3 4 5 6 7
0 0 8
0 1 8
0 0 7
2 0 8
0 0 8
2 0 8
0 0 8
2 0 8
0 0 8
2 0 8
0 0 8
1 2 5 32
0 5 7
2 4 8
0 0 8
1 0 2 0
2 1 3
0 0 1
0 1 2
0 2 3
0 3 4
0 4 5
0 5 6
0 6 7
0 7 8


output

28
28
21
11
7
7
7
2
73
0
0
5
32
5
1
1
1

*/



/*
# pythonによる愚直解

import math

N,Q = map(int,input().split())
array = list(map(int,input().split()))

for _ in range(Q):
  query = list(map(int,input().split()))
  if query[0] == 0: # sum
    ans = 0
    for i in range(query[1], query[2]):
      ans += array[i]
    print(ans)
  elif query[0] == 1:
    for i in range(query[1], query[2]):
      array[i] = query[3]
  else:
    for i in range(query[1], query[2]):
      array[i] = math.isqrt(array[i])
    
*/
yukicoder

結果

ソースコード
