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, ,

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

• +3

 » 6 days ago, # |   0 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
•  » » 5 days ago, # ^ |   0 Thanks for the help :)
 » 6 days ago, # |   0 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))/2Now 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
•  » » 5 days ago, # ^ |   0 great idea , i got it. Thanks :)