結果

問題 No.880 Yet Another Segment Tree Problem
コンテスト
ユーザー beet
提出日時 2019-09-06 20:16:21
言語 C++17
(gcc 13.3.0 + boost 1.89.0)
結果
AC  
実行時間 533 ms / 5,000 ms
コード長 3,527 bytes
記録
コンパイル時間 2,111 ms
コンパイル使用メモリ 201,500 KB
実行使用メモリ 49,788 KB
最終ジャッジ日時 2025-06-20 10:25:54
合計ジャッジ時間 11,866 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 38
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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