結果

問題 No.880 Yet Another Segment Tree Problem
コンテスト
ユーザー vjudge1
提出日時 2026-07-24 22:46:12
言語 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,745 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 941 ms
コンパイル使用メモリ 176,460 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2026-07-24 22:46:24
合計ジャッジ時間 12,118 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 31 WA * 2 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] = L[o] * (mid - l + 1);
    M[o << 1] = m[o << 1] = L[o];  // ??????/???????? L[o]
    s[o << 1 | 1] = L[o] * (r - mid);
    M[o << 1 | 1] = m[o << 1 | 1] = L[o];  // ?????
    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] = x * (r - l + 1); M[o] = m[o] = x; 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 (x == 1) return;  // ???gcd(a,1)??1???????????????
    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] = 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 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];
    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 t, l, r; long long x = 0;
        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));
    }
    return 0;
}
0