結果

問題 No.880 Yet Another Segment Tree Problem
コンテスト
ユーザー vjudge1
提出日時 2026-07-24 22:26:32
言語 C++11
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=gnu++11 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
TLE  
実行時間 -
コード長 2,041 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 879 ms
コンパイル使用メモリ 176,844 KB
実行使用メモリ 12,800 KB
最終ジャッジ日時 2026-07-24 22:26:49
合計ジャッジ時間 12,605 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int n,q;
long long a[N],s[4*N],M[4*N],m[4*N],L[4*N];
long long g(long long a,long long b){while(b){long long t=a%b;a=b;b=t;}return a;}
void p(int o,int l,int r){if(L[o]!=-1){int mid=(l+r)>>1;L[o<<1]=L[o];s[o<<1]=L[o]*(mid-l+1);M[o<<1]=L[o];m[o<<1]=L[o];L[o<<1|1]=L[o];s[o<<1|1]=L[o]*(r-mid);M[o<<1|1]=L[o];m[o<<1|1]=L[o];L[o]=-1;}}
void u(int o,int l,int r){s[o]=s[o<<1]+s[o<<1|1];M[o]=max(M[o<<1],M[o<<1|1]);m[o]=min(m[o<<1],m[o<<1|1]);}
void b(int o,int l,int r){L[o]=-1;if(l==r){s[o]=a[l];M[o]=a[l];m[o]=a[l];return;}int mid=(l+r)>>1;b(o<<1,l,mid);b(o<<1|1,mid+1,r);u(o,l,r);}
void u1(int o,int l,int r,int ql,int qr,long long x){if(ql<=l&&r<=qr){L[o]=x;s[o]=x*(r-l+1);M[o]=x;m[o]=x;return;}if(L[o]!=-1&&l<r)p(o,l,r);int mid=(l+r)>>1;if(ql<=mid)u1(o<<1,l,mid,ql,qr,x);if(qr>mid)u1(o<<1|1,mid+1,r,ql,qr,x);u(o,l,r);}
void u2(int o,int l,int r,int ql,int qr,long long x){if(L[o]!=-1&&l<r)p(o,l,r);if(ql<=l&&r<=qr){if(m[o]==M[o]){long long nv=g(m[o],x);L[o]=nv;s[o]=nv*(r-l+1);M[o]=nv;m[o]=nv;return;}int mid=(l+r)>>1;u2(o<<1,l,mid,ql,qr,x);u2(o<<1|1,mid+1,r,ql,qr,x);u(o,l,r);return;}int mid=(l+r)>>1;if(ql<=mid)u2(o<<1,l,mid,ql,qr,x);if(qr>mid)u2(o<<1|1,mid+1,r,ql,qr,x);u(o,l,r);}
long long q3(int o,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return M[o];if(L[o]!=-1&&l<r)p(o,l,r);int mid=(l+r)>>1;long long res=0;if(ql<=mid)res=max(res,q3(o<<1,l,mid,ql,qr));if(qr>mid)res=max(res,q3(o<<1|1,mid+1,r,ql,qr));return res;}
long long q4(int o,int l,int r,int ql,int qr){if(ql<=l&&r<=qr)return s[o];if(L[o]!=-1&&l<r)p(o,l,r);int mid=(l+r)>>1;long long res=0;if(ql<=mid)res+=q4(o<<1,l,mid,ql,qr);if(qr>mid)res+=q4(o<<1|1,mid+1,r,ql,qr);return res;}
int main(){scanf("%d%d",&n,&q);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);b(1,1,n);while(q--){int o,l,r;long long x;scanf("%d%d%d",&o,&l,&r);if(o==1){scanf("%lld",&x);u1(1,1,n,l,r,x);}else if(o==2){scanf("%lld",&x);u2(1,1,n,l,r,x);}else if(o==3)printf("%lld\n",q3(1,1,n,l,r));else if(o==4)printf("%lld\n",q4(1,1,n,l,r));}return 0;}
0