Susquehanna International Group

01Counting Triples

For original problem statement, pls refer to the source image down below Once upon a time, in a land where numbers roamed free, there existed a magical array that could contain as many integers as it desired. The array was curious and ever-changing, for it was governed by a series of mystical commands known as queries. Our story begins with the array starting off completely empty, a blank slate awaiting adventure. The queries came in two forms: The "+x" spell: When cast, this spell would summon the integerx and place it into the array. The array, being very welcoming, allowed multiple instances of the same integer to coexist harmoniously. The "-x" spell: This spell had the power to banish all instances of the integer x from the array, sending them away to realms unknown. After each spell was cast, the array would ponder upon the number of magical triples (x, y, z) within itself. These triples had to meet a special condition: the difference between 𝑥 and 𝑦 had to be the same as the difference between 𝑦 and 𝑧. This special difference was known as "diff." The array, being wise and meticulous, would count these triples after each query and keep track of the counts. In our tale, it is important to note that: The integers mentioned in the queries ranged from -10⁹ to 10⁹ Each "-x" query was always valid, meaning the integer 𝑥 it referred to was indeed present in the array. The number of triples for each query was guaranteed to fit into a 32-bit integer. Thus, the array embarked on its journey, processing each query and recounting its magical triples, sharing the results as it went along.

Constraints

N/A

解法

每次 +x 或 -x 操作后输出三元组 (x, y, z) 数(满足 y - x = z - y，即三数等差)。增量维护：用 multiset/计数表 + 二维表 pair_count[(d, mid)] = 以 mid 为中点、公差 d 出现的「左端点+1, 右端点 +1」配对数。+x 时，对所有公差 d，把 x 当中点时新贡献的三元组：cnt[x-d] · cnt[x+d]。-x 时反向减去。但简单实现 OA 可接受 brute force：每次操作后扫整个数组算三元组。这里给出 brute force 版本。时间 O(Q · M²)，M 为不同值数。

from typing import List
from collections import Counter

def countingTriples(queries: List[str]) -> List[int]:
    cnt: Counter[int] = Counter()
    out: List[int] = []
    for q in queries:
        sign, x = q[0], int(q[1:])
        if sign == '+':
            cnt[x] += 1
        else:
            cnt[x] = 0  # banish all instances
        # count triples (a, b, c) with b - a = c - b
        keys = sorted(k for k, v in cnt.items() if v > 0)
        total = 0
        for i, b in enumerate(keys):
            for a_idx in range(i):
                a = keys[a_idx]
                c = 2 * b - a
                if c > b and c in cnt and cnt[c] > 0:
                    total += cnt[a] * cnt[b] * cnt[c]
            # triples with a == b or b == c handled via combinations
            if cnt[b] >= 3:
                total += cnt[b] * (cnt[b] - 1) * (cnt[b] - 2) // 6
        out.append(total)
    return out

import java.util.*;

class Solution {
    int[] countingTriples(String[] queries) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int[] out = new int[queries.length];
        for (int qi = 0; qi < queries.length; qi++) {
            String q = queries[qi];
            char sign = q.charAt(0);
            int x = Integer.parseInt(q.substring(1));
            if (sign == '+') cnt.merge(x, 1, Integer::sum);
            else cnt.remove(x);
            List<Integer> keys = new ArrayList<>(cnt.keySet());
            Collections.sort(keys);
            long total = 0;
            for (int i = 0; i < keys.size(); i++) {
                int b = keys.get(i);
                long cb = cnt.getOrDefault(b, 0);
                for (int j = 0; j < i; j++) {
                    int a = keys.get(j);
                    int c = 2 * b - a;
                    if (c > b && cnt.containsKey(c)) {
                        total += (long) cnt.get(a) * cb * cnt.get(c);
                    }
                }
                if (cb >= 3) total += cb * (cb - 1) * (cb - 2) / 6;
            }
            out[qi] = (int) total;
        }
        return out;
    }
}

#include <vector>
#include <string>
#include <unordered_map>
#include <set>

class Solution {
public:
    std::vector<int> countingTriples(std::vector<std::string>& queries) {
        std::unordered_map<int, int> cnt;
        std::vector<int> out;
        for (auto& q : queries) {
            char sign = q[0];
            int x = std::stoi(q.substr(1));
            if (sign == '+') cnt[x]++;
            else cnt.erase(x);
            std::set<int> keys;
            for (auto& [k, v] : cnt) keys.insert(k);
            std::vector<int> ks(keys.begin(), keys.end());
            long long total = 0;
            for (size_t i = 0; i < ks.size(); i++) {
                int b = ks[i];
                long long cb = cnt[b];
                for (size_t j = 0; j < i; j++) {
                    int a = ks[j];
                    int c = 2 * b - a;
                    auto it = cnt.find(c);
                    if (c > b && it != cnt.end()) {
                        total += (long long) cnt[a] * cb * it->second;
                    }
                }
                if (cb >= 3) total += cb * (cb - 1) * (cb - 2) / 6;
            }
            out.push_back((int) total);
        }
        return out;
    }
};

02Equal Difference Pairs

See the Image Source section at the bottom of this page for the original problem descritpion and example explanation :) Imagine two friends, Alice and Bob, who both have lists of numbers. They want to play a game to see how many special pairs they can find. Each pair consists of two numbers, one from Alice's list and one from Bob's list. But there's a twist: they are only interested in pairs where a certain condition is met.

Example 1

Input:

a = [2, -2, 5, 3]
b = [1, 5, -1, 1]

Output:

Explanation: For (i, j) = (0, 0) equality holds: a[0] - b[0] = 2 - 1 = 1 and a[0] - b[0] = 2 - 1 = 1 For (i, j) = (0, 1) equality holds: a[0] - b[1] = 2 - 5 = -3 and a[1] - b[0] = -2 - 1 = -3 For (i, j) = (0, 2) equality doesn't hold: a[0] - b[2] = 2 - (-1) = 3 and a[2] - b[0] = 5 - 1 = 4 For (i, j) = (0, 3) equality doesn't hold: a[0] - b[3] = 2 - 1 = 1 and a[3] - b[0] = 3 - 1 = 2 For (i, j) = (1, 1) equality holds: a[1] - b[1] = (-2) - 5 = -7 and a[1] - b[1] = -2 - 5 = -7 For (i, j) = (1, 2) equality does not holds: a[1] - b[2] = (-2) - (-1) = -1 and a[2] - b[1] = 5 - 5 = 0 For (i, j) = (1, 3) equality does not holds: a[1] - b[3] = (-2) - 1 = -3 and a[3] - b[1] = 3 - 5 = -2 For (i, j) = (2, 2) equality holds: a[2] - b[2] = 5 - (-1) = 6 and a[2] - b[2] = 5 - (-1) = 6 For (i, j) = (2, 3) equality holds: a[2] - b[3] = 5 - 1 = 4 and a[3] - b[2] = 3 - (-1) = 4 For (i, j) = (3, 3) equality holds: a[3] - b[3] = 3 - 1 = 2 and a[3] - b[3] = 3 - 1 = 2

Example 2

Input:

a = [25, 0]
b = [0, 25]

Output:

Explanation: n/a

解法

求满足 a[i] - b[j] == a[j] - b[i] 的 (i, j) 对(i ≤ j)，变形得 a[i] + b[i] == a[j] + b[j]。对每个下标 i 算 s[i] = a[i] + b[i]，用哈希表按 s 值分桶，每桶 k 个元素贡献 C(k, 2) + k(包括 i==j 自配对，按题目示例需要)。时间 O(n)，空间 O(n)。

from typing import List
from collections import Counter

def equalDifferencePairs(a: List[int], b: List[int]) -> int:
    sums = [a[i] + b[i] for i in range(len(a))]
    cnt = Counter(sums)
    total = 0
    for c in cnt.values():
        total += c * (c - 1) // 2 + c  # ordered pairs (i, j) with i <= j
    return total

import java.util.*;

class Solution {
    long equalDifferencePairs(int[] a, int[] b) {
        Map<Long, Long> cnt = new HashMap<>();
        for (int i = 0; i < a.length; i++) {
            long s = (long) a[i] + b[i];
            cnt.merge(s, 1L, Long::sum);
        }
        long total = 0;
        for (long c : cnt.values()) total += c * (c - 1) / 2 + c;
        return total;
    }
}

#include <vector>
#include <unordered_map>

class Solution {
public:
    long long equalDifferencePairs(std::vector<int>& a, std::vector<int>& b) {
        std::unordered_map<long long, long long> cnt;
        for (size_t i = 0; i < a.size(); i++) cnt[(long long) a[i] + b[i]]++;
        long long total = 0;
        for (auto& [k, c] : cnt) total += c * (c - 1) / 2 + c;
        return total;
    }
};