**NOTE — This problen is not the from any ongoing contest.** You are given an array of N integers. X[i] is the number of distinct values that occur to the left of index i and not on or to the right of index i. Y[i] is the number of distinct values that occur to the right of index i and not on or to the left of index i. Determine the absolute difference of X[i] , Y[i] for every index 1 <= i <= N. ****Constraint**** 1<=T<=10 1<=N<=2*10^5 -10^9<=Ai<=10^9

You can't just say

without stating

whereyou got it from. That's extremely sus.However, I think this is from Ode 2 Code Round 2, which has already ended, so I think it's safe to put a solution here. I won't until someone else confirms it though.

So,if the contest has already ended,then I think you can share your solution.

Put a link to the contest and proof that it has ended, otherwise I cannot let myself post the solution knowing that you may be cheating.

The contest was ODE 2 CODE ,on visiting the site again it says you cannot attend this test as it has already ended.And I don't know how to add screenshot so that I can give you proof.

Yeah, I can confirm this is from Ode 2 code only.

Now it has been 3 days to post this question and there are so many great coders at this community, so plz anyone can tell me how to solve this question?

Seems to work on my tests, but I don't have ways to verify it) ~~~~~

Spoiler~~~~~

Although you have added comments in your code but can you plz elaborate your thought process what you have done.

To solve this problem we need to 1) calculate values in array X, 2) calculate values in array Y, 3) get answer by counting absolute differens between |X[i] — Y[i]|.

Actually method of calculating values in array X and Y is almost the same (you can see that in code, for X we just start from the beginning and for Y from the end). So the only thing we need to understand is how to calculate array X.

What is the value of the first element X[0]? Obviously it is 0, as there are no items before element at 0 position. And what is the answer for X[1]? If there no elements equal to arr[0] in range [1, n) X[1] = 1, otherwise X[1] = 0. So basicly to find out X[i] we need to know the value of X[i-1] and how many times arr[i] occurs in range (i, n).

One of the way to do it is using MAP. (if constraints would allow, we actually could use simple array, where at some index j we will keep how many times j occurs in arr (for example if we have arr = [1,2,2,5,4,5,3,5], our array that count how many times each element occurs would be [0, 1, 2, 1, 1, 3]), but we cannot create such big array (10^9) as we will get TimeLimit or MemoryLimit, so we will use map.) Now for some position i we know if element arr[i-1] will occur later in the array. If it will, we don't need to do anything, but if is won't X[i] = X[i-1] + 1. Thats it! I wrote a little bit overcomplicated code, adding easier version with some comments.

SpoilerI thinks maintaining 2 map ( 1 for the left part (initially empty) and other for the right-part (initially contains all elements)) and when you iterate from left to right you have to increase the left[a[i]]++ and right[a[i]]-- ( and when right[a[i]]==0 then just erase it from the right map). and just take the difference between the size of these two map and just print it for each indexes.

I think this will work if i am not wrong.

Anyone got test link for round 3?

Me

For each a

_{i}, find it's contribution to X[i] and Y[i]. Something like : for a_{i}, all i > last occurence of a_{i}, it will contribute in X. Similarly for Y