记录编号	617728	评测结果	AAAAAAAAAA
题目名称	2371.[HDU4902]数据结构难题	最终得分	100
用户昵称	ChenBp	是否通过	通过
代码语言	C++	运行时间	4.001 s
提交时间	2026-07-24 16:20:49	内存使用	4.78 MiB

#include <iostream>
using namespace std;
const int N = 5e5 + 5;
int mx[4 * N], lz[4 * N], a[N];
int gcd(int x, int y) { return y == 0 ? x : gcd(y, x % y); }
#define mid ((l + r) / 2)
#define lc (u * 2)
#define rc (u * 2 + 1)
void lazy(int u, int v) {
    mx[u] = v;
    lz[u] = v;
}
void pd(int u) {
    if (lz[u] != -1) {
        lazy(lc, lz[u]);
        lazy(rc, lz[u]);
        lz[u] = -1;
    }
}
void build(int u, int l, int r) {
    lz[u] = -1;
    if (l == r) {
        mx[u] = a[l];
        return;
    }
    build(lc, l, mid);
    build(rc, mid + 1, r);
    mx[u] = max(mx[lc], mx[rc]);
}
void update(int u, int l, int r, int xl, int xr, int v) {
    if (xl <= l && r <= xr) {
        lazy(u, v);
        return;
    }
    pd(u);
    if (xl <= mid) update(lc, l, mid, xl, xr, v);
    if (xr > mid) update(rc, mid + 1, r, xl, xr, v);
    mx[u] = max(mx[lc], mx[rc]);
}
void updateg(int u, int l, int r, int xl, int xr, int v) {
    if (mx[u] <= v) return;
    if (xl <= l && r <= xr) {
        if (l == r) {
            mx[u] = gcd(mx[u], v);
            return;
        }
        if (lz[u] != -1) {
            lazy(u, gcd(lz[u], v));
            return;
        }
    }
    pd(u);
    if (xl <= mid) updateg(lc, l, mid, xl, xr, v);
    if (xr > mid) updateg(rc, mid + 1, r, xl, xr, v);
    mx[u] = max(mx[lc], mx[rc]);
}
void print(int u, int l, int r) {
    if (l == r) {
        cout << mx[u] << " ";
        return;
    }
    pd(u);
    print(lc, l, mid);
    print(rc, mid + 1, r);
}
#undef mid
#undef lc
#undef rc
int main() {
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) cin >> a[i];
        build(1, 1, n);
        int q;
        cin >> q;
        while (q--) {
            int op, l, r, x;
            cin >> op >> l >> r >> x;
            if (op == 1) {
                update(1, 1, n, l, r, x);
            } else {
                updateg(1, 1, n, l, r, x);
            }
        }
        print(1, 1, n);
        // cout << "\n";
    }
    return 0;
}