This task can be solved online with O(log(n)^2) per query and O(log(n)) per update with merge sort tree. It's offline version has O(n*log(n)) solution for all queries, but as I can see you need to do it online.

Notice that the problem is same as adding one to cell (x, y) and summing the rectangle (1, 1) → (a, b). If either one of them is negative you can just add some offset.

Now, if either one of x or y is bounded by M, then you can use Compressed 2D Binary Indexed Tree to get complexity, however with O(N + M) memory complexity. If M is too big, you can still do it in O(N) memory but that'll add another factor in time complexity (use map for those M ordered sets).

There is another solution, when both x and y is big, then you can adapt the solution of the problem "Game" from IOI 2013. That was basically updating an index on a grid, and finding gcd of a subgrid, but grid size can be 10¹⁸ × 10¹⁸. It has solution with complexity , and memory .

I think you can use binary partition here.

Let's have a data structure that can solve this problem: He have an array of pairs such that its sorted by the first element already and one kind of query : For a pair (a,b) count how many elements have x <= a and y <=b. We can solve this easy version with a binary search on index of bigger i such that the value is bigger than a and waveleet tree (i don't know how big the values can be, but i am assuming that they are big).

So we can turn the original problem in versions of this problem, lets make log(Q) buckets such that:

• Bucket i have at most 2^i elements
• You always insert elements in bucket 0
• If a bucket have more than the allowed value, we throw every value in this bucket to the next one and clear the current bucket

So now, in every bucket we maintain a vector of pairs such that they are sorted by the first value (x) and a data-structure that allow us to query (in such case, waveleet tree), if we have an query of type 2, we will pass for every bucket, in every bucket we will do as follow:

• Binary Search on the rightmost-guy with x <= a, let this guy be i
• Query in the waveleet tree for the subarray [1..i] for guys <= y

The answer will be the maximum of the answers in every bucket

For type one query we will do as follow:

• Add in first bucket (x,y) (this guy can have at most 2^i guys)
• Sort the first bucket
• If this bucket have more than 2^0 guys, merge sort with the second bucket (don't care about the second element in the pair, just keep they sorted by the first) and clear the current bucket.
• While the current group have more than allowed, keep merging with the next and clearing, and every time that you throw some guys at the next group, rebuild the waveleet of this group.

Lets see the complexity for every query:

• We will rebuild the i-th group at most Q/2^(i-1) * 2^i = Q*2 , since we will rebuild log(Q) times, this will be Q*log(Q)
• For every bucket i, we need to binary search the rightmost guy with x<=a (this is log(2^i)) and query in waveleet tree (this will be log(2^i) too), so we have to do this for every one of the log(Q) buckets, this will be log(Q)*log(N)

For the trivia part, i think you can refeer to this and keep tracking where every element is.

Árbol 2D, que funciona en O({log²}N) por query. No se me ocurre nada mejor que eso. Perdón.

About the online solution: At the beginning imagine you have infinite number of empty BST-s. When you add a pair (a, b), you insert b in the BST with index a. And you can keep a dynamic segment tree over all numbers. Let me explain it clear: in a node in the segment tree, which is responsible for [left; right], you store a BST with all the numbers from all the BST-s with indexes in the range [left; right]. Now I think that the adding of a pair is clear. And so is the erase (instead of inserting in the BST, you just erase). But the query seems a little problem. Let our query is (a, b). Then will ask the segment tree to find the number of elements smaller than b in the range [0; a]. So it is only left to find the number of elements smaller that b in a BST. I think that this is also clear. About the BST i recommend treap, but you can also use AVL or something else.