結果

問題 No.880 Yet Another Segment Tree Problem
ユーザー beetbeet
提出日時 2019-09-06 20:16:21
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 515 ms / 5,000 ms
コード長 3,527 bytes
コンパイル時間 2,291 ms
コンパイル使用メモリ 209,120 KB
実行使用メモリ 50,080 KB
最終ジャッジ日時 2023-10-24 02:37:32
合計ジャッジ時間 11,603 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 13 ms
46,692 KB
testcase_01 AC 15 ms
46,752 KB
testcase_02 AC 15 ms
46,732 KB
testcase_03 AC 16 ms
46,732 KB
testcase_04 AC 15 ms
46,732 KB
testcase_05 AC 15 ms
46,760 KB
testcase_06 AC 14 ms
46,732 KB
testcase_07 AC 16 ms
46,764 KB
testcase_08 AC 15 ms
46,764 KB
testcase_09 AC 16 ms
46,732 KB
testcase_10 AC 15 ms
46,764 KB
testcase_11 AC 408 ms
49,640 KB
testcase_12 AC 398 ms
49,680 KB
testcase_13 AC 283 ms
49,608 KB
testcase_14 AC 389 ms
49,776 KB
testcase_15 AC 428 ms
49,776 KB
testcase_16 AC 442 ms
49,792 KB
testcase_17 AC 515 ms
50,080 KB
testcase_18 AC 497 ms
50,080 KB
testcase_19 AC 169 ms
49,776 KB
testcase_20 AC 172 ms
50,068 KB
testcase_21 AC 172 ms
49,752 KB
testcase_22 AC 168 ms
49,792 KB
testcase_23 AC 176 ms
49,760 KB
testcase_24 AC 155 ms
49,776 KB
testcase_25 AC 159 ms
50,068 KB
testcase_26 AC 159 ms
49,752 KB
testcase_27 AC 161 ms
49,792 KB
testcase_28 AC 162 ms
49,760 KB
testcase_29 AC 379 ms
49,776 KB
testcase_30 AC 415 ms
49,776 KB
testcase_31 AC 440 ms
49,792 KB
testcase_32 AC 137 ms
50,080 KB
testcase_33 AC 130 ms
49,776 KB
testcase_34 AC 135 ms
49,784 KB
testcase_35 AC 128 ms
49,776 KB
testcase_36 AC 128 ms
49,800 KB
testcase_37 AC 129 ms
49,792 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

using ll = long long;

struct T{
  ll ma,lcm,len,sum;
  T(){}
  T(ll ma,ll lcm,ll len,ll sum):ma(ma),lcm(lcm),len(len),sum(sum){}
};
using E = ll;

const ll INF = 1e9+1;
ll mgcd(ll x,ll y){
  if(x<y) swap(x,y);
  while(ll z=x%y){
    x=y;
    y=z;
  }
  return y;
}
ll mul(ll x,ll y){
  //return (__int128_t)x*y>=INF?INF:x*y;
  //return x>=(INF+y-1)/y?INF:x*y<INF?x*y:INF;
  return x*y>=INF?INF:x*y;
}
ll mlcm(ll x,ll y){
  if(x>=INF||y>=INF) return INF;
  return mul(x/mgcd(x,y),y);
};
T f(const T &a,const T &b){
  return T(max(a.ma,b.ma),
           mlcm(a.lcm,b.lcm),
           a.len+b.len,
           a.sum+b.sum);
};
T g(const T &a,E b){
  return T(b,b,a.len,a.len*b);
};
const int MAX = 1<<20;
T ti(-INF,1,0,0);
E ei(-1);
T dat[MAX];
E laz[MAX<<1];

int n,height;

void init(int n_){
  n=1;height=0;
  while(n<n_) n<<=1,height++;
  fill(dat,dat+MAX,ti);
  fill(laz,laz+MAX,ei);
}
void build(const vector<T> &v){
  int n_=v.size();
  init(n_);
  for(int i=0;i<n_;i++) dat[n+i]=v[i];
  for(int i=n-1;i;i--)
    dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
}
inline T reflect(int k){
  return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
}
inline void eval(int k){
  if(laz[k]==ei) return;
  laz[(k<<1)|0]=laz[k];
  laz[(k<<1)|1]=laz[k];
  dat[k]=g(dat[k],laz[k]);
  laz[k]=ei;
}
inline void thrust(int k){
  for(int i=height;i;i--) eval(k>>i);
}
inline void recalc(int k){
  while(k>>=1)
    dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
}
void update(int a,int b,E x){
  thrust(a+=n);
  thrust(b+=n-1);
  for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
    if(l&1) laz[l]=x,l++;
    if(r&1) --r,laz[r]=x;
  }
  recalc(a);
  recalc(b);
}
void set_val(int a,T x){
  thrust(a+=n);
  dat[a]=x;laz[a]=ei;
  recalc(a);
}
T query(int a,int b){
  thrust(a+=n);
  thrust(b+=n-1);
  T vl=ti,vr=ti;
  for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
    if(l&1) vl=f(vl,reflect(l++));
    if(r&1) vr=f(reflect(--r),vr);
  }
  return f(vl,vr);
}
ll update_gcd(int a,int b,E x,int l,int r,int k){
  eval(k);
  if(r<=a||b<=l||x%dat[k].lcm==0) return -1;
  if(a<=l&&r<=b&&dat[k].ma*dat[k].len==dat[k].sum){
    ll z=dat[k].lcm;
    laz[k]=mgcd(dat[k].lcm,x);
    eval(k);
    return z/dat[k].lcm;
  }
  int m=(l+r)>>1;
  ll p=update_gcd(a,b,x,l,m,(k<<1)|0);
  ll q=update_gcd(a,b,x,m,r,(k<<1)|1);
  if(a<=l&&r<=b&&dat[k].lcm<INF){
    dat[k].ma=max(dat[(k<<1)|0].ma,dat[(k<<1)|1].ma);
    dat[k].sum=dat[(k<<1)|0].sum+dat[(k<<1)|1].sum;
    ll r=p/mgcd(p,q)*q;
    dat[k].lcm/=r;
    return r;
  }
  dat[k]=f(dat[(k<<1)|0],dat[(k<<1)|1]);
  return -1;
}
void update_gcd(int a,int b,E x){
  update_gcd(a,b,x,0,n,1);
}

struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

//INSERT ABOVE HERE
signed main(){
  int n,q;
  cin>>n>>q;
  vector<int> as(n);
  for(int i=0;i<n;i++) cin>>as[i];

  vector<T> vt;
  for(int i=0;i<n;i++) vt.emplace_back(as[i],as[i],1,as[i]);
  build(vt);

  for(int i=0;i<q;i++){
    int t;
    cin>>t;
    if(t==1){
      int l,r,x;
      cin>>l>>r>>x;
      l--;
      update(l,r,x);
    }
    if(t==2){
      int l,r,x;
      cin>>l>>r>>x;
      l--;
      update_gcd(l,r,x);
    }
    if(t==3){
      int l,r;
      cin>>l>>r;
      l--;
      cout<<query(l,r).ma<<"\n";
    }
    if(t==4){
      int l,r;
      cin>>l>>r;
      l--;
      cout<<query(l,r).sum<<"\n";
    }
  }
  cout<<flush;
  return 0;
}
0