这道题恶心之处在于区间向下取整。
这里给出两种思路：
区间覆盖做法
如果最大值和最小值向下取整后相等，则对此区间进行区间覆盖。
我考场写的是这个，但是码错了，加上习惯不好,\(100\to64\),再加上烦了弱智错误，\(64\to9\)，不给出代码。
差值相等做法
注意到相邻两数的向下取整的差值不可能大于 \(1\)，也就是：
\[\lfloor \frac x k\rfloor-\lfloor \frac {x-1} k\rfloor \leq 1 \]稍微推广一下，我们得到：
\[x-1-\lfloor \frac {x-1} k\rfloor \leq x-\lfloor \frac x k\rfloor \]这说明从整点来看，函数\(f(x)=x-\lfloor \frac x k\rfloor\) 具有单调上升的特点。
如果区间内\(f(\max)=f(\min)\)，那么区间内所需要减去的差值必定相等，之间减去即可。
考虑到向下取整在进行多次后必然使数值、区间差值趋于 \(0\)，因此时间复杂度维持在 \(O(n\log n)\)左右，可参考犇犇给出势能分析法。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const LL N = 1e5 + 5;
const LL inf = 1e18;
LL n, m, a[N], op, l, r, d;
struct node {
LL l, r, len, mn, mx, sum, lz;
} t[N * 25];
LL fl(LL x, LL y) {
if (0 <= x)
return x / y;
return -((-x + y - 1) / y);
}
void add(LL pos, LL k) {
t[pos].lz += k;
t[pos].sum += k * t[pos].len;
t[pos].mn += k, t[pos].mx += k;
}
void pushup(LL pos) {
t[pos].mn = min(t[pos * 2].mn, t[pos * 2 + 1].mn);
t[pos].mx = max(t[pos * 2].mx, t[pos * 2 + 1].mx);
t[pos].sum = t[pos * 2].sum + t[pos * 2 + 1].sum;
}
void down(LL pos) {
if (t[pos].lz != 0) {
LL k = t[pos].lz, l = pos * 2, r = pos * 2 + 1;
add(l, k), add(r, k);
t[pos].lz = 0;
}
}
void build(LL pos, LL l, LL r) {
t[pos].l = l, t[pos].r = r, t[pos].len = (r - l + 1);
if (l == r) {
t[pos].mx = t[pos].mn = t[pos].sum = a[l];
return;
}
LL mid = (l + r) / 2;
build(pos * 2, l, mid), build(pos * 2 + 1, mid + 1, r);
pushup(pos);
}
void upd1(LL pos, LL l, LL r, LL k) {
if (t[pos].r < l || r < t[pos].l)
return;
if (l <= t[pos].l && t[pos].r <= r) {
add(pos, k);
return;
}
down(pos);
upd1(pos * 2, l, r, k), upd1(pos * 2 + 1, l, r, k);
pushup(pos);
}
void upd2(LL pos, LL l, LL r, LL k) {
if (t[pos].r < l || r < t[pos].l)
return;
if (l <= t[pos].l && t[pos].r <= r && t[pos].l == t[pos].r) {
t[pos].mn = t[pos].mx = t[pos].sum = fl(t[pos].sum, k);
return;
}
down(pos);
if (l <= t[pos].l && t[pos].r <= r && t[pos].mn - fl(t[pos].mn, k) == t[pos].mx - fl(t[pos].mx, k)) {
add(pos, fl(t[pos].mx, k) - t[pos].mx);
return;
}
upd2(pos * 2, l, r, k), upd2(pos * 2 + 1, l, r, k);
pushup(pos);
}
LL querymn(LL pos, LL l, LL r) {
if (t[pos].r < l || r < t[pos].l)
return inf;
if (l <= t[pos].l && t[pos].r <= r)
return t[pos].mn;
down(pos);
return min(querymn(pos * 2, l, r), querymn(pos * 2 + 1, l, r));
}
LL querysum(LL pos, LL l, LL r) {
if (t[pos].r < l || r < t[pos].l)
return 0;
if (l <= t[pos].l && t[pos].r <= r)
return t[pos].sum;
down(pos);
return querysum(pos * 2, l, r) + querysum(pos * 2 + 1, l, r);
}
int main() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld", &a[i]);
}
build(1, 1, n);
for (int i = 1; i <= m; i++) {
scanf("%lld", &op);
if (op == 1) {
scanf("%lld%lld%lld", &l, &r, &d);
l++, r++;
upd1(1, l, r, d);
}
if (op == 2) {
scanf("%lld%lld%lld", &l, &r, &d);
l++, r++;
upd2(1, l, r, d);
}
if (op == 3) {
scanf("%lld%lld", &l, &r);
l++, r++;
printf("%lld\n", querymn(1, l, r));
}
if (op == 4) {
scanf("%lld%lld", &l, &r);
l++, r++;
printf("%lld\n", querysum(1, l, r));
}
}
return 0;
}