Problem Brief

Counting Triples

INTERNOA

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.

𖤣𖥧𖡼𓋼𖤣𖥧𓋼 🌱 Credit to ʚrobotɞ 🌱 𖤣𖥧𖡼𓋼𖤣𖥧𓋼ଓ༉

1Example 1

Input

queries = ["+4", "+5", "+6", "+4", "+3", "-4"], difference = 1

Output

[0, 0, 1, 2, 4, 0]

Explanation

Let us follow the journey of the array as it processes the following queries: ["+4", "+5", "+6", "+4", "+3", "-4"] with a diff of 1. The goal is to count the number of triples after each query. First Query: "+4" The array welcomes the number 4, making it numbers = [4]. No triples exist yet, so the count is 0. Second Query: "+5" The array welcomes the number 5, making it numbers = [4, 5]. Still, no triples can be formed, so the count remains 0. Third Query: "+6" The array welcomes the number 6, making it numbers = [4, 5, 6]. The numbers can now form one triple (6, 5, 4) that meets the condition (6 - 5 = 1 = 5 - 4). The count of triples is now 1. Fourth Query: "+4" Another number 4 is added, making the array numbers = [4, 5, 6, 4]. There are now two ways to form the triple (6, 5, 4). The count of triples increases to 2. Fifth Query: "+3" The array welcomes the number 3, making it numbers = [4, 5, 6, 4, 3]. Now, there are two ways to form the triple (6, 5, 4) and two ways to form the triple (5, 4, 3). The count of triples rises to 4. Sixth Query: "-4" The number 4 is banished from the array, making it numbers = [5, 6, 3]. With no 4s left, no triples can meet the condition anymore. The count of triples drops to 0. The enchanted array’s journey through these queries leads to the final counts: [0, 0, 1, 2, 4, 0]. And so, the array continues its magical adventure, ever ready for new queries and the mysteries they bring.