3943. Number of Pairs After Increment

 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;

    }

};