1.Problem
Number of Pairs After Increment - LeetCode
2.Idea
Use sqrt decomposition to maintain the segment element frequency count which also supports range update
3.Code
class Solution {
public:
vector<int> numberOfPairs(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
int n = nums2.size();
int k = sqrt(n);
int N = (n+k-1)/k;
vector<long long>nums22(nums2.begin(), nums2.end());
vector<unordered_map<long long, int>>arr(N);
vector<long long>add(N, 0);
// 1. Initialize blocks
for(int i = 0; i < N; ++i)
for(int j = i*k; j < min((i+1)*k, n); ++j)
++arr[i][nums2[j]];
vector<int>rt;
rt.reserve(queries.size());
for(auto& q : queries)
{
if(q[0] == 1) // Range Addition
{
int st = q[1], end = q[2];
long long val = q[3];
for(int i = st; i <= end; ++i)
{
int idx = i/k;
// Fully covered block: apply lazy tag
if((i % k) == 0 && i + k - 1 <= end)
{
add[idx] += val;
i += k-1; // Jump to the end of the block
}
else // Partially covered block: manual update
{
--arr[idx][nums22[i]];
// Pruning: prevent hash map bloat
if(arr[idx][nums22[i]] == 0) arr[idx].erase(nums22[i]);
nums22[i] += val;
++arr[idx][nums22[i]];
}
}
}
else // Query Pairs
{
int c = 0;
for(auto& num : nums1)
{
for(int i = 0; i < N; ++i)
{
// Calculate required target considering the block's lazy tag
long long tar = q[1] - num - add[i];
// Use find() to avoid accidental zero-value insertions
if(arr[i].find(tar) != arr[i].end())
c += arr[i][tar];
}
}
rt.push_back(c);
}
}
return rt;
}
};
