Problem with Queries
Contest: Educational Codeforces Round 173 (Rated for Div. 2)
Difficulty rating: 3000
Tags: brute force, data structures, implementation

You are given an array $$$a$$$, consisting of $$$n$$$ integers. Your task is to process $$$q$$$ queries of two types:

- $$$1~p~x$$$ — set the value of the element at index $$$p$$$ equal to $$$x$$$;
- $$$2~l~r$$$ — count the number of pairs of indices $$$(i, j)$$$ such that $$$l \le i < j \le r$$$ and $$$a_i \ne a_j$$$.

Note that the queries in this task are encoded; each subsequent query can only be decoded after calculating the answer to the preceding query of the second type.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le n$$$).

The third line contains a single integer $$$q$$$ ($$$1 \le q \le 3 \cdot 10^5$$$) — the number of queries.

The next $$$q$$$ lines describe the queries in one of the following formats:

- $$$1~p'~x'$$$ ($$$0 \le p', x' \le n-1$$$);
- $$$2~l'~r'$$$ ($$$0 \le l', r' \le n-1$$$).

The queries are encoded as follows: let $$$\mathit{last}$$$ be the answer to the latest processed query of the second type (initially, $$$\mathit{last} = 0$$$).

- if the type of the query is $$$1$$$, then $$$p = ((p' + \mathit{last}) \bmod n) + 1$$$, $$$x = ((x' + \mathit{last}) \bmod n) + 1$$$.
- if the type of the query is $$$2$$$, $$$l = ((l' + \mathit{last}) \bmod n) + 1$$$, $$$r = ((r' + \mathit{last}) \bmod n) + 1$$$. If $$$l > r$$$, swap their values.

Don't forget to update the value of $$$\mathit{last}$$$ after answering each query of the second type.

Additional constraint on the input: there is at least one query of the second type.

Output format:
For each query of the second type, print the answer — the number of pairs of indices $$$(i, j)$$$ such that $$$l \le i < j \le r$$$ and $$$a_i \ne a_j$$$.

Constraints:
Time limit: 8.0 s
Memory limit: 1024.0 MB

Note:
In the first example, the actual queries (after decoding) are:

- 2 1 3
- 1 1 3
- 2 1 3
- 1 2 3
- 2 1 3

Example input:
3
1 2 3
5
2 0 2
1 0 2
2 0 2
1 2 0
2 1 0

Example output:
3 2 0

Example input:
7
1 3 4 4 7 1 3
3
2 1 6
2 1 0
2 5 6

Example output:
13 18 0

Editorial:
First, let's reformulate the problem. Instead of counting the number of pairs of distinct elements in a segment, we will count the number of pairs of identical elements and subtract it from the total number of pairs. To solve this problem, we will use square root decomposition on the array.
Let's divide the original array into blocks of size $$$B$$$ and learn how to answer queries $$$(l, r)$$$ that satisfy the following conditions:
• $$$l = L \cdot B$$$ — this means that the left boundary of the query coincides with the beginning of some block of the square root decomposition;
• $$$r = R \cdot B - 1$$$ — this means that the right boundary of the query coincides with the last element of some block of the square root decomposition.
Due to this restriction on the problem, we can utilize certain properties that will be necessary for our solution:
• The order of elements within a block does not matter; we can treat each block of our square root decomposition as an unordered multiset;
• Changing the value of an element in terms of a multiset can be reformulated as removing the old value and adding the new value.
In general, the modified queries can be rewritten in the following format:
1. add $$$ind~x$$$ — add an element with value $$$x$$$ to the block $$$ind$$$.
2. del $$$ind~x$$$ — remove an element with value $$$x$$$ from the block $$$ind$$$.
3. get $$$L~R$$$ — count the number of pairs of positions $$$(i, j)$$$, where $$$L \cdot B \le i < j \le R \cdot B$$$ and $$$a_i = a_j$$$.
Let's assume we have an array $$$blocks[i][j]$$$, which stores the answer to the third type of query for all possible segments of blocks $$$0 \le i \le j \le K$$$, where $$$K$$$ is the number of blocks in the square root decomposition of our array. Initially, we fill the $$$blocks$$$ array with zeros and then add all elements using the add operation.
Let's observe how the first type of query modifies this array; the second type of query is considered similarly. When an element with value $$$x$$$ is added to the block $$$ind$$$, it affects all elements of the array $$$blocks[i][j]$$$ such that $$$0 \le i \le ind \le j$$$.
For a specific element of the array $$$blocks[i][j]$$$, its value increases by the number of occurrences of the element $$$x$$$ in the segment $$$[i \cdot B; j \cdot B]$$$. This happens because the added element can form a pair with all existing elements equal to the specified value that belong to this segment. Formally, this can be described as $$$blocks[i][j]~=blocks[i][j] + count(i, j, x)$$$, where $$$count(i, j, x)$$$ is a function that returns the number of occurrences of the element $$$x$$$ in the blocks $$$i, \dots, j$$$. The function $$$count(i, j, x)$$$ can be maintained by storing an array $$$pref[val][i]$$$, where for each element $$$val$$$, it will store how many times it appears in the segment of blocks $$$[0, i]$$$.
When adding an element, the number of values that need to be recalculated will be about $$$\frac{K \cdot (K - 1)}{2}$$$. If we can do this in $$$O(1)$$$, we can achieve a solution in $$$O((Q+N) \cdot N^{\frac{2}{3}}$$$, taking $$$B = N^{\frac{2}{3}}$$$. Unfortunately, it is practically impossible to fit this within time limits, so let's try to improve the solution.
Returning to the description of how to modify an arbitrary element of the array $$$blocks[i][j]$$$, let's rewrite and transform the formula:
into
The second term in this expression does not use the right boundary $$$j$$$, and the third term does not use the left boundary $$$i$$$. Suppose we want to add the second term to the relevant elements $$$blocks[i][j]$$$; we can iterate over the left boundary $$$i$$$ and add $$$count(i, ind, x)$$$ for all right boundaries where $$$j \ge ind$$$.
To perform such additions in $$$O(1)$$$, we will use something like a difference array: we will create an array $$$update\_right[i][j]$$$, where for a fixed left boundary, we will store how the suffix of right boundaries will change. When iterating over the left boundary $$$i$$$, for the suffix of right boundaries $$$j \ge ind$$$, we need to add the same amount $$$count(i, ind, x)$$$; but we will handle this addition on the suffix in one position of the array $$$update\_right[i][ind] = update\_right[i][ind] + count(i, ind, x)$$$.
Then, to account for these additions in the third type of queries $$$get(L,~ R)$$$, we will need to take the sum of the elements of the array $$$update\_right[L][L] + update\_right[L][L + 1] + \dots + update\_right[L][R]$$$.
The third term from the sum $$$blocks[i][j]~=blocks[i][j] + count(i, ind, x) + count(ind + 1, j, x)$$$ is processed similarly: we will iterate over the right boundary and form an array $$$update\_left$$$, where the additions will be on the prefix.
Thus, each modification query will be executed in $$$O(K)$$$. A query of the third type requires us to iterate over one of the fixed boundaries and find the sum, which will require $$$O(K)$$$ operations. By choosing $$$B = \sqrt N$$$, each of these queries can be executed in $$$O(\sqrt N)$$$.
Returning to the original problem, let's describe how to find the answer to a query whose boundaries do not coincide with the boundaries of the blocks:
1. First, find the answer for the problem we learned to solve above for the largest segment of blocks that is completely contained within the query;
2. Now, we need to add the contribution of $$$O(B)$$$ elements from the blocks that are not fully included in the query.
Each of these $$$O(B)$$$ elements can form a pair with all elements in our block segment, so we will need to take the number of occurrences of this element from the $$$pref$$$ array. Additionally, these $$$O(B)$$$ elements can form pairs with each other; to handle this, we can maintain an array of size $$$N$$$, where for each value, we keep track of the number of additional elements with that value. When processing some additional element $$$x$$$, we will add the count of these elements from the array to the answer and increase this count by $$$1$$$; at the end of processing the query for all additional elements, we will reset their count back to $$$0$$$.
Thus, we have obtained a solution in $$$O((N+Q) \cdot \sqrt N)$$$.