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

• 問題: No.3507 RangeSum RangeUpdate RangeSqrt
• ユーザー: tau1235
• 提出日時: 2026-04-18 00:01:36
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,411 bytes
• コンパイル時間: 4,053 ms
• コンパイル使用メモリ: 352,612 KB
• 実行使用メモリ: 30,956 KB
• 最終ジャッジ日時: 2026-04-18 00:02:26
• 合計ジャッジ時間: 14,987 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

ファイルパターン	結果
sample	-- * 1
other	AC * 1 TLE * 2 -- * 26

ソースコード

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

template<typename S,S (*op)(S,S),S (*e)(),typename F,S (*mapping)(F,S),F (*composition)(F,F),F (*id)()>
struct SegTreeBeats{
  int n,log,sz;
  vector<S> node;
  vector<F> lazy;
  SegTreeBeats(int n){*this=SegTreeBeats<S,op,e,F,mapping,composition,id>(vector<S>(n,e()));}
  SegTreeBeats(vector<S> v){
    sz=v.size();
    n=1;log=0; while (n<sz) n*=2,log++;
    node.assign(2*n,e());
    lazy.assign(2*n,id());
    for (int i=0;i<sz;i++) node[i+n]=v[i];
    for (int i=n-1;i>=1;i--) update(i);
  }

  void update(int x){node[x]=op(node[x*2],node[x*2+1]);}
  void all_apply(int x,F f){
    node[x]=mapping(f,node[x]);
    if (x<n){
      lazy[x]=composition(f,lazy[x]);
      if (node[x].fail) push(x),update(x);
    }
  }
  void push(int x){
    if (x<=0) return;
    all_apply(x*2,lazy[x]);
    all_apply(x*2+1,lazy[x]);
    lazy[x]=id();
  }

  void set(int x,S val){
    x+=n;
    for (int i=log;i>=1;i--) push(x>>i);
    node[x]=val;
    for (int i=1;i<=log;i++) update(x>>i);
  }

  S get(int x){
    x+=n;
    for (int i=log;i>=1;i--) push(x>>i);
    return node[x];
  }

  void apply(int x,F f){
    x+=n;
    for (int i=log;i>=1;i--) push(x>>i);
    node[x]=mapping(f,node[x]);
    for (int i=1;i<=log;i++) update(x>>i);
  }
  void apply(int l,int r,F f){
    if (l==r) return;
    l+=n;r+=n;
    for (int i=log;i>=1;i--){
      if (((l>>i)<<i)!=l) push(l>>i);
      if (((r>>i)<<i)!=r) push((r-1)>>i);
    }
    int l2=l,r2=r;
    while (l<r){
      if (l%2==1) all_apply(l++,f);
      if (r%2==1) all_apply(--r,f);
      l>>=1;r>>=1;
    }
    l=l2;r=r2;
    for (int i=1;i<=log;i++){
      if (((l>>i)<<i)!=l) update(l>>i);
      if (((r>>i)<<i)!=r) update((r-1)>>i);
    }
  }

  S prod(int l,int r){
    if (l==r) return e();
    l+=n;r+=n;
    for (int i=log;i>=1;i--){
      if (((l>>i)<<i)!=l) push(l>>i);
      if (((r>>i)<<i)!=r) push((r-1)>>i);
    }
    S suml=e(),sumr=e();
    while (l<r){
      if (l%2==1) suml=op(suml,node[l++]);
      if (r%2==1) sumr=op(node[--r],sumr);
      l>>=1;r>>=1;
    }
    return op(suml,sumr);
  }

  template<bool (*f)(S)>
  int max_right(int l=0){
    if (l==sz) return sz;
    l+=n;
    S p=e();
    for (int i=log;i>=1;i--) push(l>>i);
    while (true){
      while (l%2==0) l>>=1;
      if (!(f(op(p,node[l])))){
        while (l<n){
          push(l);
          l<<=1;
          if (f(op(p,node[l]))){
            p=op(p,node[l]);
            l++;
          }
        }
        return l-n;
      }
      p=op(p,node[l]);
      l++;
      if ((l&-l)==l) break;
    }
    return sz;
  }
};

using ll=long long;
unordered_map<ll,ll> mp;
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 (mp.count(n)) return mp[n];
    if (n == 0){
        return 0;
    } else {
        unsigned long long a = isqrt_aux(( 63 - __builtin_clzll(n)) / 2, n);
        return mp[n]=(n <= a * a - 1 ? a - 1 : a);
    }
}

struct S{
  ll val;
  ll sz;
  bool same;
  ll sameval;
  bool fail;
};
S op(S a,S b){
  bool nsame=a.same&&b.same;
  if (nsame&&!(a.sz==0||b.sz==0)) nsame=a.sameval==b.sameval;
  return S{a.val+b.val,a.sz+b.sz,nsame,max(a.sameval,b.sameval),!nsame};
}
S e(){return S{0,0,true,-1,false};};
struct F{
  ll cnt;
  ll x;
};
S mapping(F f,S x){
  if (f.x!=-1){
    x.val=f.x*x.sz;
    x.same=true;
    x.sameval=f.x;
    x.fail=false;
  } 
  if (f.cnt==0) return x;
  if (x.fail) return x;
  assert(x.same);
  while (f.cnt--&&x.sameval>1) x.sameval=isqrt(x.sameval);
  x.val=x.sameval*x.sz;
  return x;
}
F composition(F f,F g){
  if (f.x==-1){
    g.cnt+=f.cnt;
    return g;
  }
  return F{f.cnt,f.x};
}
F id(){return F{0,-1};}

int main(){
  int n,q;
  cin>>n>>q;
  vector<ll> a(n);
  vector<S> v(n);
  for (int i=0;i<n;i++){
    cin>>a[i];
    v[i]={a[i],1,true,a[i],false};
  }
  SegTreeBeats<S,op,e,F,mapping,composition,id> seg(v);
  while (q--){
    int t;
    cin>>t;
    if (t==0){
      int l,r;
      cin>>l>>r;
      auto p=seg.prod(l,r);
      cout<<p.val<<endl;
    }
    if (t==1){
      int l,r,x;
      cin>>l>>r>>x;
      seg.apply(l,r,F{0,x});
    }
    if (t==2){
      int l,r;
      cin>>l>>r;
      seg.apply(l,r,F{1,-1});
    }
  }
}