#1173880 (C++14) No.880 Yet Another Segment Tree Problem

• 問題: No.880 Yet Another Segment Tree Problem
• ユーザー: zelda_master
• 提出日時: 2026-07-27 20:41:49
• 言語: C++14 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 231 ms / 5,000 ms
• コード長: 3,952 bytes
• コンパイル時間: 575 ms
• コンパイル使用メモリ: 83,112 KB
• 実行使用メモリ: 12,544 KB
• 最終ジャッジ日時: 2026-07-27 20:42:07
• 合計ジャッジ時間: 6,921 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 38

ソースコード

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 100010;

struct Node {
    int l, r, val, lcm, ma;
    LL sum;
};

int n, q, a[N];

int GCD(int x, int y) {
    return y ? GCD(y, x % y) : x;
}

int LCM(int x, int y) {
    return 1LL * x / GCD(x, y) * y;
}

struct SegTree {
    Node seg[N << 2];
    int Len(int u) { return seg[u].r - seg[u].l + 1; }
    void PushUp(int u) {
        seg[u].ma = max(seg[u << 1].ma, seg[u << 1 | 1].ma);
        seg[u].sum = seg[u << 1].sum + seg[u << 1 | 1].sum;
        seg[u].lcm = LCM(seg[u << 1].lcm, seg[u << 1 | 1].lcm);
        if (seg[u << 1].val && seg[u << 1].val == seg[u << 1 | 1].val) seg[u].val = seg[u << 1].val;
        else seg[u].val = 0;
    }
    void PushDown(int u) {
        if (seg[u].val) {
            seg[u << 1].ma= seg[u << 1].lcm = seg[u << 1].val = seg[u].val;
            seg[u << 1 | 1].ma = seg[u << 1 | 1].lcm = seg[u << 1 | 1].val = seg[u].val;
            seg[u << 1].sum = 1LL * seg[u].val * Len(u << 1);
            seg[u << 1 | 1].sum = 1LL * seg[u].val * Len(u << 1 | 1);
            seg[u].val = 0;
        }
    }
    void Build(int u, int l, int r) {
        seg[u] = { l, r, 0, 0, 0, 0LL };
        if (l == r) {
            seg[u].val = seg[u].lcm = seg[u].ma = seg[u].sum = a[l];
            return;
        }
        int mid = l + r >> 1;
        Build(u << 1, l, mid), Build(u << 1 | 1, mid + 1, r);
        PushUp(u);
    }
    void Modify(int u, int l, int r, int v) {
        if (l <= seg[u].l && seg[u].r <= r) {
            seg[u].ma = seg[u].lcm = seg[u].val = v;
            seg[u].sum = 1LL * v * Len(u);
            return;
        }
        PushDown(u);
        int mid = seg[u].l + seg[u].r >> 1;
        if (mid >= l) Modify(u << 1, l, r, v);
        if (mid + 1 <= r) Modify(u << 1 | 1, l, r, v);
        PushUp(u);
    }
    void ModifyGCD(int u, int l, int r, int v) {
        if (l <= seg[u].l && seg[u].r <= r) {
            if (seg[u].lcm && v % seg[u].lcm == 0) return;
            if (seg[u].val) {
                seg[u].ma = seg[u].lcm = seg[u].val = GCD(seg[u].val, v);
                seg[u].sum = 1LL * GCD(seg[u].val, v) * Len(u);
                return;
            }
        }
        PushDown(u);
        int mid = seg[u].l + seg[u].r >> 1;
        if (mid >= l) ModifyGCD(u << 1, l, r, v);
        if (mid + 1 <= r) ModifyGCD(u << 1 | 1, l, r, v);
        PushUp(u);
    }
    int QueryMax(int u, int l, int r) {
        if (l <= seg[u].l && seg[u].r <= r) return seg[u].ma;
        PushDown(u);
        int mid = seg[u].l + seg[u].r >> 1;
        int ret = 0;
        if (mid >= l) ret = max(ret, QueryMax(u << 1, l, r));
        if (mid + 1 <= r) ret = max(ret, QueryMax(u << 1 | 1, l, r));
        return ret;
    }
    LL QuerySum(int u, int l, int r) {
        if (l <= seg[u].l && seg[u].r <= r) return seg[u].sum;
        PushDown(u);
        int mid = seg[u].l + seg[u].r >> 1;
        LL ret = 0LL;
        if (mid >= l) ret += QuerySum(u << 1, l, r);
        if (mid + 1 <= r) ret += QuerySum(u << 1 | 1, l, r);
        return ret;
    }
};
SegTree sgt;

int main() {
    // freopen("gcdmax.in", "r", stdin);
    // freopen("gcdmax.out", "w", stdout);

    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    
    sgt.Build(1, 1, n);
    while (q--) {
        int op;
        scanf("%d", &op);
        if (op == 1) {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            sgt.Modify(1, l, r, x);
        } else if (op == 2) {
            int l, r, x;
            scanf("%d%d%d", &l, &r, &x);
            sgt.ModifyGCD(1, l, r, x);
        } else if (op == 3) {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d\n", sgt.QueryMax(1, l, r));
        } else {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%lld\n", sgt.QuerySum(1, l, r));
        }
    }

    return 0;
}