thảo luận Leetcode + Codeforces, Competitive programming contest. Đường tới Guardian + Candidate Master.

class SqrtDecomposition:
    def __init__(self, arr):
        n = len(arr)
        self.arr = arr
        self.blockSize = int(math.sqrt(n)) + 1
        self.numBlocks = math.ceil(n/self.blockSize)
       
        self.block = [[] for _ in range(self.numBlocks)]
        self.counter = [defaultdict(int) for _ in range(self.numBlocks)]
        self.lazy = [0] * self.numBlocks
       
        for i, val in enumerate(arr):
            b_idx = i // self.blockSize
            self.block[b_idx].append(val)
            self.counter[b_idx][val] += 1
   
    def addRange(self, left, right, val):
        l = left // self.blockSize
        r = right // self.blockSize
       
        if l == r:
            leftStart = left % self.blockSize
            rightEnd = right % self.blockSize
           
            for i in range(leftStart, rightEnd + 1):
                old_val = self.block[l][i]
                self.counter[l][old_val] -= 1
                self.block[l][i] += val
                self.counter[l][old_val + val] += 1
        else:
            # Left partial block
            leftStart = left % self.blockSize
            for i in range(leftStart, len(self.block[l])):
                old_val = self.block[l][i]
                self.counter[l][old_val] -= 1
                self.block[l][i] += val
                self.counter[l][old_val + val] += 1

            # Middle full blocks
            for i in range(l + 1, r):
                self.lazy[i] += val

            # Right partial block
            rightEnd = right % self.blockSize
            for i in range(0, rightEnd + 1):
                old_val = self.block[r][i]
                self.counter[r][old_val] -= 1
                self.block[r][i] += val
                self.counter[r][old_val + val] += 1

    def count(self, num):
        ans = 0
        for i in range(self.numBlocks):
            target = num - self.lazy[i]
            ans += self.counter[i][target]

        return ans

class Solution:
    def numberOfPairs(self, nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
        counter1 = Counter(nums1)
        tot = []
        seg = SqrtDecomposition(nums2)
       
        for q in queries:
            if q[0] == 2:
                t = q[1]
                ans = 0
               
                for num, freq in counter1.items():
                    ans += freq * seg.count(t - num)

                tot.append(ans)
            else:
                x, y, val = q[1], q[2], q[3]
                seg.addRange(x, y, val)
               
        return tot