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;  
   }  
 };