题目
题解
将 \(n\) 个元素的数组 \(a\) 按块长 \(\sqrt{n}\) 进行分块处理。为每个块设置一个懒添加标记 \(add[i]\)，代表这个区间每个元素共同添加的数值大小。
对于任意一个无序数组，想要维护出该数组内小于某个值的元素个数，时间复杂度都将来到 \(O(n)\)；对于任意一个有序数组，想要维护出该数组内小于某个值的元素个数，可以使用时间复杂度为 \(O(logn)\) 的二分法来维护。
对于每个块，都将数据拷贝到一个备份数组，随后将备份数组进行排序，单个块该操作时间复杂度为 \(O(\sqrt{n} + \sqrt{n}log\sqrt{n})\)。
若查询覆盖块 \(i\) 的全部元素，那么只需要对块 \(i\) 的备份数组进行二分查找出小于等于 \(c^2 - add[i]\) 的元素个数，单次操作时间复杂度 \(O(log\sqrt{n})\)，此类块至多只有 \(\sqrt{n}\) 块，最差时间复杂度 \(O(\sqrt{n}log\sqrt{n})\)；若查询未覆盖块 \(i\) 的全部元素，那么可以暴力维护出原数列小于等于 \(c^2 - add[i]\) 的元素个数，单次操作时间复杂度 \(O(\sqrt{n})\)，此类块至多只有 \(2\) 块，最差时间复杂度 \(O(2\sqrt{n})\)。
对于区间加操作，将添加值存储在符合整块都进行加法操作的块的懒标记 \(add[i]\) 上，单次操作时间复杂度 \(O(1)\)，此类块至多只有 \(\sqrt{n}\) 块，最差时间复杂度 \(O(\sqrt{n})\)；未符合整块都进行加法操作则进行暴力处理，但是执行完加法后会破坏备份数组的有序性，需要重新备份且排序，单次操作时间复杂度 \(O(2\sqrt{n} + \sqrt{n}log\sqrt{n})\)，此类块至多只有 \(2\) 块，最差时间复杂度 \(O(4\sqrt{n} + 2\sqrt{n}log\sqrt{n})\)。
参考代码
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int n;//数列元素个数
int op, l, r;
int len;//块长
ll c;
ll a[50005];//数列
ll b[50005];//排序后的数列
ll add[230];//懒添加标记
int lidx[230];//块的左下标
int ridx[230];//块的右下标
/*初始化块*/
void initPieces() {
len = sqrt(n);
memcpy(b + 1, a + 1, sizeof(ll) * n);//拷贝一份原数列
for (int i = 1, j = 1; i <= n; i += len, ++ j) {
lidx[j] = i;//左闭
ridx[j] = min(i + len, n + 1);//右开
sort(b + lidx[j], b + ridx[j]);//为当前块排序
}
}
/*获取下标 x 所在的块的索引*/
int getPieceId(int x) {
return (x - 1) / len + 1;
}
/*判断下标 x 是否为块的左边界*/
bool isLeftBoundary(int x) {
return (x - 1) % len == 0;
}
/*判断下标 x 是否为块的右边界*/
bool isRightBoundary(int x) {
return x % len == 0;
}
int main() {
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; ++ i) cin >> a[i];
initPieces();
for (int i = 0; i < n; ++ i) {
cin >> op >> l >> r >> c;
bool isLe = isLeftBoundary(l), isRi = isRightBoundary(r);
int le = getPieceId(l), ri = getPieceId(r);
if (op) {
int res = 0;
c = c * c;
for (int i = isLe ? le : le + 1, j = isRi ? ri : ri - 1; i <= j; ++ i) {
res += lower_bound(b + lidx[i], b + ridx[i], c - add[i]) - b - lidx[i];
}
if (!isLe) {
while (l <= r) {
res += a[l] + add[le] < c;
if (isRightBoundary(l)) break;
++ l;
}
}
if (!isRi) {
while (l <= r) {
res += a[r] + add[ri] < c;
if (isLeftBoundary(r)) break;
-- r;
}
}
cout << res << '\n';
} else {
for (int i = isLe ? le : le + 1, j = isRi ? ri : ri - 1; i <= j; ++ i) add[i] += c;
if (!isLe) {
//根号 n 时间复杂度重构第 le 块
while (l <= r) {
a[l] += c;
if (isRightBoundary(l)) break;
++ l;
}
memcpy(b + lidx[le], a + lidx[le], sizeof(ll) * (ridx[le] - lidx[le]));
sort(b + lidx[le], b + ridx[le]);
}
if (!isRi) {
//根号 n 时间复杂度重构第 ri 块
while (l <= r) {
a[r] += c;
if (isLeftBoundary(r)) break;
-- r;
}
memcpy(b + lidx[ri], a + lidx[ri], sizeof(ll) * (ridx[ri] - lidx[ri]));
sort(b + lidx[ri], b + ridx[ri]);
}
}
}
return 0;
}