結果

問題 No.3507 RangeSum RangeUpdate RangeSqrt
コンテスト
ユーザー Kurao
提出日時 2026-04-22 09:20:12
言語 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  
実行時間 -
コード長 2,428 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 5,264 ms
コンパイル使用メモリ 288,572 KB
実行使用メモリ 13,968 KB
最終ジャッジ日時 2026-04-22 09:20:31
合計ジャッジ時間 14,317 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 28
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include<iostream>
#include<vector>
#include<array>
#include<queue>
#include<cmath>
#include<atcoder/all>

using namespace std;
using namespace atcoder;
#define overload4(_1,_2,_3,_4,name,...) name

#define rep1(i,n) for (int i = 0; i < (n); ++i)
#define rep2(i,m,n) for (int i = (m); i < (n); ++i)
#define rep3(i,m,n,k) for (int i = (m); i < (n); i += (k))

#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)

#define inf 1000000000

vector<pair<int,int>> dij = {{0,1}, {1,0}, {0,-1}, {-1,0}};

using mint = modint998244353;
int isqrt(int n){
    double x=sqrt(n);
    int ans=(int)x;
    while ((ans+1)*(ans+1)<=n){
        ans++;
    }
    return ans;
};
struct S{
    int cnt_0;
    int cnt_1;
    array<int,5> fi;
};

S op(S x,S y){
    array<int,5> ans;
    rep (i,5){
        ans[i]=x.fi[i]+y.fi[i];
    }
    return S{x.cnt_0+y.cnt_0,x.cnt_1+y.cnt_1,ans};
};

S conv(int x){
    if (x==0){
        return S{1,0,{0,0,0,0,0}};
    } else {
        array<int,5> ans;
        ans[0]=x;
        rep(i,1,5){
            ans[i]=isqrt(ans[i-1]);
        }
        return S{1,1,ans};
    }
};

S rot(S x){
    array<int,5> ans;
    rep(i,4){
        ans[i]=x.fi[i+1];
    }
    ans[4]=x.cnt_1;
    return S{x.cnt_0,x.cnt_1,ans};
};

S mapping(int f,S x){
    if (f==-inf){
        return x;
    } else if (f<0) {
        S now=x;
        rep (i,-f){
            now=rot(now);
        }
        return now;
    } else {
        S ans=conv(f);
        array<int,5> final;
        rep(i,5){
            final[i]=ans.fi[i]*x.cnt_0;
        }
        return S{ans.cnt_0*x.cnt_0,ans.cnt_1*x.cnt_0,final};
    }
};

int composition(int f,int g){
    if (f==-inf){
        return g;
    } else if (g==-inf){
        return f;
    } else if (f>=0){
        return f;
    } else if (g>=0){
        return mapping(f,conv(g)).fi[0];
    } else {
        return f+g;
    }
};

S e(){
    return S{0,0,{0,0,0,0,0}};
}

int id(){
    return -inf;
};

int main(){
    int n,q;
    cin>>n>>q;
    vector<S> a(n);
    rep(_,n){
        int i;
        cin>>i;
        a[_]=conv(i);
    }
    lazy_segtree<S,op,e,int,mapping,composition,id> seg(a);
    rep(_,q){
        int t,l,r;
        cin>>t>>l>>r;
        if (t==0){
            cout<<seg.prod(l,r).fi[0]<<endl;
        } else if (t==1){
            int x;
            cin>>x;
            seg.apply(l,r,x);
        } else {
            seg.apply(l,r,-1);
        }
    }
}
0