Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

imstark007's blog

By imstark007, history, 6 days ago, In English,

can anyone give idea , how to solve question 4 in order of time complexity N , atcoder beginner contest 159. Link: https://atcoder.jp/contests/abc159/tasks/abc159_d

 
 
 
 
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's precalculate numbers of choices for every $$$1 \le n \le 2 * 10^5$$$ and store it somewhere (there's simple formula like: $$$\frac{cnt_i(cnt_{i} - 1)}{2}$$$). Let's say that $$$ans$$$ is sum of such numbers. Now we can answer each query with $$$O(1)$$$ $$$-$$$ we have overall answer and just need to recalculate answer in current point $$$a_1, a_2, \dots, a_n$$$ and change our answer according it.

If you don't get my bad English you can see my submission

»
6 days ago, # |
  Vote: I like it 0 Vote: I do not like it

First take a map, iterate through array once and calculate number of balls for each number i.e. m[a[i]]++;

Now iterate through map and calculate sum of number of ways of choosing 2 balls for each number for(auto i:m) total_count+=((i.second)(i.second-1))/2

Now all you need to do is to go through the array one more time and print total_count-m[a[i]]*(m[a[i]]-1)/2+(m[a[i]]-1)*(m[a[i]]-2)/2 for each element.

Idea is to first subtract number of ways of choosing two balls from m[a[i]] balls and then add number of ways of choosing two balls from m[a[i]]-1 balls.

code link