#1173303 (C++11) No.880 Yet Another Segment Tree Problem

• 問題: No.880 Yet Another Segment Tree Problem
• ユーザー: vjudge1
• 提出日時: 2026-07-24 22:59:39
• 言語: C++11 (gcc 15.2.0 + boost 1.90.0)
• 結果: TLE
• 実行時間: -
• コード長: 2,983 bytes
• コンパイル時間: 1,006 ms
• コンパイル使用メモリ: 179,224 KB
• 実行使用メモリ: 12,672 KB
• 最終ジャッジ日時: 2026-07-24 22:59:52
• 合計ジャッジ時間: 11,877 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 33 TLE * 1 -- * 4

ソースコード

#include <bits/stdc++.h>
#define int long long
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];
inline int rd() {
    int x = 0, f = 1;
    char c = getchar();
    while (!isdigit(c)) { if (c == '-') f = -f; c = getchar(); }
    while (isdigit(c)) { x = x * 10 + c - 48; c = getchar(); }
    return x * f;
}
inline void wt(int x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) wt(x / 10);
    putchar(x % 10 + 48);
}
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];
    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 == 0) return;
    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;
}
signed main() {
    n = rd(); q = rd();
    for (int i = 1; i <= n; i++) a[i] = rd();
    b(1, 1, n);
    while (q--) {
        int t = rd(), l = rd(), r = rd();
        if (t == 1) { long long x = rd(); u1(1, 1, n, l, r, x); }
        else if (t == 2) { long long x = rd(); u2(1, 1, n, l, r, x); }
        else if (t == 3) { wt(q3(1, 1, n, l, r)); putchar('\n'); }
        else { wt(q4(1, 1, n, l, r)); putchar('\n'); }
    }
    return 0;
}