結果

問題 No.880 Yet Another Segment Tree Problem
コンテスト
ユーザー vjudge1
提出日時 2026-07-24 22:27:43
言語 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
結果
WA  
実行時間 -
コード長 2,148 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 896 ms
コンパイル使用メモリ 176,468 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2026-07-24 22:27:59
合計ジャッジ時間 12,259 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other AC * 2 WA * 31 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){return b?g(b,a%b):a;}
void p(int o,int l,int r){
    if(L[o]==-1)return;
    int mid=(l+r)>>1;
    L[o<<1]=L[o<<1|1]=L[o];
    s[o<<1]=M[o<<1]=m[o<<1]=L[o]*(mid-l+1);
    s[o<<1|1]=M[o<<1|1]=m[o<<1|1]=L[o]*(r-mid);
    L[o]=-1;
}
void u(int o){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]=M[o]=m[o]=a[l];return;}
    int mid=(l+r)>>1;
    b(o<<1,l,mid);b(o<<1|1,mid+1,r);
    u(o);
}
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]=M[o]=m[o]=x*(r-l+1);return;}
    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);
}
void u2(int o,int l,int r,int ql,int qr,long long x){
    if(ql<=l&&r<=qr){
        long long G1=g(M[o],x),G2=g(m[o],x);
        if(G1==G2){L[o]=G1;s[o]=G1*(r-l+1);M[o]=m[o]=G1;return;}
        if(M[o]==m[o]){long long nv=g(M[o],x);L[o]=nv;s[o]=nv*(r-l+1);M[o]=m[o]=nv;return;}
    }
    p(o,l,r);
    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);
}
long long q3(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return M[o];
    p(o,l,r);
    int mid=(l+r)>>1;long long R=0;
    if(ql<=mid)R=max(R,q3(o<<1,l,mid,ql,qr));
    if(qr>mid)R=max(R,q3(o<<1|1,mid+1,r,ql,qr));
    return R;
}
long long q4(int o,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr)return s[o];
    p(o,l,r);
    int mid=(l+r)>>1;long long R=0;
    if(ql<=mid)R+=q4(o<<1,l,mid,ql,qr);
    if(qr>mid)R+=q4(o<<1|1,mid+1,r,ql,qr);
    return R;
}
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 t,l,r;long long x;
        scanf("%d%d%d",&t,&l,&r);
        if(t==1)scanf("%lld",&x),u1(1,1,n,l,r,x);
        else if(t==2)scanf("%lld",&x),u2(1,1,n,l,r,x);
        else if(t==3)printf("%lld\n",q3(1,1,n,l,r));
        else printf("%lld\n",q4(1,1,n,l,r));
    }
}
0