QBALL - Balls and Queries
Xima has N balls arranged together in a line, the i-th (1 ≤ i ≤ N) ball has a value of Ai.
Tzaph asks Q queries to Xima. There are two types of queries:
- 1 i k: The value of the i-th ball is changed into k. In other words, Ai = k. Take note that Ai and k could have a same value. In this case, Xima shouldn't do anything.
- 2 i: Tzaph removes the i-th ball out from the line. Print the number of pairs (x, y) such that the x-th and the y-th ball is in the line, x < y, and Ax = Ay. After this query, Tzaph returns the i-th ball back to the line in its original position.
However, Tzaph asks too many queries and Xima has too many balls. Xima asks you to help him answer all of Tzaph's queries. Help him out!
Input
The first line contains two integers N and Q.
The second line consists of N integers, where the i-th integer represents Ai.
The next Q lines represents the queries with format explained in the description.
Output
For every second type of query, print the answer required.
Constraints
1 ≤ N, Q, Ai, k ≤ 105
Examples
Input 1: 5 5 1 2 3 4 5 1 2 3 1 5 4 2 1 1 2 4 2 4 Output 1: 2 1
Input 2: 1 3 1 2 1 1 1 3 2 1 Output 2: 0 0
hide comments
Vipul Srivastava:
2020-05-21 18:51:11
@maximath_1 can you please check my submission once and let me know if I am totally wrong or I am missing some tests? I am kind of stuck here...
|
|
nadstratosfer:
2020-05-21 16:06:10
Statement implies ordering of the values that is not conveyed intuitively by story about balls in a bag, please consider rephrasing it. Also get rid of formatting that makes samples invisible in dark mode, see the screenshot at KONSTRAKSCHION.
|
Added by: | Maximilliano |
Date: | 2020-05-21 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | Own problem, a buffed version of https://atcoder.jp/contests/abc159/tasks/abc159_d |