結果

問題 No.880 Yet Another Segment Tree Problem
コンテスト
ユーザー vjudge1
提出日時 2026-07-24 23:02:09
言語 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  
実行時間 -
コード長 5,089 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 978 ms
コンパイル使用メモリ 181,336 KB
実行使用メモリ 12,928 KB
最終ジャッジ日時 2026-07-24 23:02:22
合計ジャッジ時間 11,732 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 33 TLE * 1 -- * 4
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005;
namespace fast_IO {
#define IOSIZE 100000
    char ibuf[IOSIZE], obuf[IOSIZE], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;
#define getchar() ((p1==p2)and(p2=(p1=ibuf)+fread(ibuf,1,IOSIZE,stdin),p1==p2)?(EOF):(*p1++))
#define putchar(x) ((p3==obuf+IOSIZE)&&(fwrite(obuf,p3-obuf,1,stdout),p3=obuf),*p3++=x)
#define isdigit(ch) (ch>47&&ch<58)
#define isspace(ch) (ch<33)
    template<typename T> inline T read() { T s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s * w; }
    template<typename T> inline bool read(T &s) { s = 0; int w = 1; char ch; while (ch = getchar(), !isdigit(ch) and (ch != EOF)) if (ch == '-') w = -1; if (ch == EOF) return false; while (isdigit(ch)) s = s * 10 + ch - 48, ch = getchar(); return s *= w, true; }
    template<typename T> inline void print(T x) { if (x < 0) putchar('-'), x = -x; if (x > 9) print(x / 10); putchar(x % 10 + 48); }
    inline bool read(char &s) { while (s = getchar(), isspace(s)); return true; }
    inline bool read(char *s) { char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) *s++ = ch, ch = getchar(); *s = '\000'; return true; }
    inline void print(char x) { putchar(x); }
    inline void print(char *x) { while (*x) putchar(*x++); }
    inline void print(const char *x) { for (int i = 0; x[i]; i++) putchar(x[i]); }
    inline bool read(std::string& s) { s = ""; char ch; while (ch = getchar(), isspace(ch)); if (ch == EOF) return false; while (!isspace(ch)) s += ch, ch = getchar(); return true; }
    inline void print(std::string x) { for (int i = 0, n = x.size(); i < n; i++) putchar(x[i]); }
    inline bool read(bool &b) { char ch; while(ch=getchar(), isspace(ch)); b=ch^48; return true; }
    inline void print(bool b) { putchar(b+48); }
    template<typename T, typename... T1> inline int read(T& a, T1&... other) { return read(a) + read(other...); }
    template<typename T, typename... T1> inline void print(T a, T1... other) { print(a), print(other...); }
    struct Fast_IO { ~Fast_IO() { fwrite(obuf, p3 - obuf, 1, stdout); } } io;
    template<typename T> Fast_IO& operator >> (Fast_IO &io, T &b) { return read(b), io; }
    template<typename T> Fast_IO& operator << (Fast_IO &io, T b) { return print(b), io; }
#define cout io
#define cin io
#define endl '\n'
} using namespace fast_IO;
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];
    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() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    b(1, 1, n);
    while (q--) {
        int t, l, r; long long x = 0;
        cin >> t >> l >> r;
        if (t == 1) { cin >> x; u1(1, 1, n, l, r, x); }
        else if (t == 2) { cin >> x; u2(1, 1, n, l, r, x); }
        else if (t == 3) cout << q3(1, 1, n, l, r) << endl;
        else cout << q4(1, 1, n, l, r) << endl;;
    }
    return 0;
}
0