考虑到每次除法,然后加法,差距会变小,于是维护加法lazytag即可
#include <cstdio>
#include <cmath>
#define int long long
int read() {
int x = 0;
bool f = 0;
char c = getchar();
while (c < 48) f ^= (c == '-'), c = getchar();
while (c > 47) x = x * 10 + (c - 48), c = getchar();
return f ? -x : x;
}
int n, m;
const int maxn = 1e5 + 51;
int a[maxn];
int mn[maxn << 2], mx[maxn << 2];
int del[maxn << 2], sum[maxn << 2];
int min(int x, int y) { return x < y ? x : y; }
int max(int x, int y) { return x > y ? x : y; }
void pushup(int rt) {
mn[rt] = min(mn[rt << 1], mn[rt << 1 | 1]);
mx[rt] = max(mx[rt << 1], mx[rt << 1 | 1]);
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void build(int l, int r, int rt) {
if (l == r) {
sum[rt] = mn[rt] = mx[rt] = a[l];
return;
}
int mid = l + r >> 1;
build(l, mid, rt << 1);
build(mid + 1, r, rt << 1 | 1);
pushup(rt);
}
void pushtag(int l, int r, int rt, int x) {
del[rt] += x, mn[rt] += x, mx[rt] += x;
sum[rt] += x * (r - l + 1);
}
void pushd(int l, int r, int rt) {
if (!del[rt]) return;
int mid = l + r >> 1;
pushtag(l, mid, rt << 1, del[rt]);
pushtag(mid + 1, r, rt << 1 | 1, del[rt]);
del[rt] = 0;
}
void modify(int a, int b, int l, int r, int rt, int v) {
if (a <= l && r <= b) {
pushtag(l, r, rt, v);
return;
}
pushd(l, r, rt);
int mid = l + r >> 1;
if (a <= mid) modify(a, b, l, mid, rt << 1, v);
if (b > mid) modify(a, b, mid + 1, r, rt << 1 | 1, v);
pushup(rt);
}
void div(int a, int b, int l, int r, int rt, int v) {
if (a <= l && r <= b) {
int tx = floor((double)mx[rt] / v);
int ty = floor((double)mn[rt] / v);
if (tx - mx[rt] == ty - mn[rt]) {
pushtag(l, r, rt, tx - mx[rt]);
return;
}
pushd(l, r, rt);
int mid = l + r >> 1;
div(a, b, l, mid, rt << 1, v), div(a, b, mid + 1, r, rt << 1 | 1, v);
pushup(rt);
return;
}
pushd(l, r, rt);
int mid = l + r >> 1;
if (a <= mid) div(a, b, l, mid, rt << 1, v);
if (b > mid) div(a, b, mid + 1, r, rt << 1 | 1, v);
pushup(rt);
}
int qry(int a, int b, int l, int r, int rt) {
if (a <= l && r <= b) return sum[rt];
pushd(l, r, rt);
int mid = l + r >> 1;
int ans = 0;
if (a <= mid) ans = qry(a, b, l, mid, rt << 1);
if (b > mid) ans += qry(a, b, mid + 1, r, rt << 1 | 1);
return ans;
}
int qrymin(int a, int b, int l, int r, int rt) {
if (a <= l && r <= b) return mn[rt];
pushd(l, r, rt);
int mid = l + r >> 1;
int ans = 1e18;
if (a <= mid) ans = min(ans, qrymin(a, b, l, mid, rt << 1));
if (b > mid) ans = min(ans, qrymin(a, b, mid + 1, r, rt << 1 | 1));
return ans;
}
signed main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) a[i] = read();
build(1, n, 1);
while (m--) {
int op;
op = read();
if (op == 1) {
int l, r, x;
l = read(), r = read(), x = read();
++l, ++r;
modify(l, r, 1, n, 1, x);
}
if (op == 2) {
int l, r, x;
l = read(), r = read(), x = read();
++l, ++r;
div(l, r, 1, n, 1, x);
}
if (op == 3) {
int l, r;
l = read(), r = read();
++l, ++r;
printf("%lld\n", qrymin(l, r, 1, n, 1));
}
if (op == 4) {
int l, r;
l = read(), r = read();
++l, ++r;
printf("%lld\n", qry(l, r, 1, n, 1));
}
}
return 0;
}