1.分块#
1.1总体思考#
1.2 题目记录#
1.2.1 LC 3943 递增后的数对数量 链接 ↗#
题目要实现两种操作
-
- 区间加x
-
- 查询区间内x的数量
对于区间操作来说，最容易想到的是线段树，但是线段树维护区间内每个数的数量非常麻烦，并且可能复杂度也不够好。分块在这种场景下较为合适，分块的区间加操作比线段树复杂度高一些，但是查询操作的复杂度更低，更加平衡。
对于区间加操作与查询操作的时间复杂度都是根号级别的，分块的思想就是将数组划分为若干个大小为的块，每个块内维护一些额外的信息来支持快速的区间加和查询操作。
题解代码
class Solution
{
static constexpr int MX = 1'000'000'001;
public:
vector<int> numberOfPairs(vector<int> &nums1, vector<int> &nums2, vector<vector<int>> &queries)
{
int n = nums1.size(), m = nums2.size();
int B = sqrt(m * n);
vector<tuple<int, int, unordered_map<int, int>, int>> blocks;
for (int i = 0; i < m; i += B)
{
int r = min(i + B, m);
unordered_map<int, int> cnt;
for (int j = i; j < r; j++)
{
cnt[nums2[j]]++;
}
blocks.emplace_back(i, r, cnt, 0);
}
vector<int> ans;
for (auto &q : queries)
{
if (q[0] == 1)
{
int l = q[1], r = q[2] + 1, val = q[3];
for (auto &[bl, br, cnt, add] : blocks)
{
if (bl >= r)
{
break;
}
if (br <= l|| add >= MX)
{
continue;
}
if (l <= bl && br <= r)
{
add = min(add + val, MX);
continue;
}
int L = max(bl, l), R = min(br, r);
for (int j = L; j < R; j++)
{
cnt[nums2[j]]--;
nums2[j] = min(nums2[j] + val, MX);
cnt[nums2[j]]++;
}
}
}
else
{
int res = 0;
for (auto &[l, r, cnt, add] : blocks)
{
int tar = q[1] - add;
for (int x : nums1)
{
auto it = cnt.find(tar - x);
if (it != cnt.end())
{
res += it->second;
}
}
}
ans.push_back(res);
}
}
return ans;
}
};