By A.K.Goharshady, 9 years ago, ,
This one can be solved in O(nlgn) using a segment tree.
First we convert all powers to numbers in range 0..n-1 to avoid working with segments as large as 109 in our segment tree. Then for each of the men we should find number of men who are placed before him and have more power let's call this gr[j]. When ever we reach a man with power x we add the segment [0,x-1] to our segment tree , so finding gr[j] can be done by querying power of j in our segment tree when it's updated by all j-1 preceding men.
Now let's call number of men who are standing after j but are weaker than j as le[j]. These values can be found using the same method with a segment-tree or in O(n) time using direct arithmetic:
le[j]=(power of j -1)-(i-1-gr[j])
note that powers are in range 0..n-1 now.
Now we can count all triplets i,j,k which have j as their second index. This is le[j]*gr[j]
so the final answer is

( \sum_{j=0}^{n-1} le[j]\times gr[j] )

• +1

 9 years ago, # |   0 Why didnt you write tutorial in "all-in-one" post? Anyway, tutorial is written good! Thanks
 9 years ago, # | ← Rev. 2 →   +9 I wrote in 5 different posts , because some people want to read the tutorial of only one problem and want to solve other problems on their own
•  9 years ago, # ^ |   0 That's why it'll be great if a Spoiler will appear here. :-)
•  9 years ago, # ^ |   0 Thanks a lot for your turoial! I do not understand the meaning of le[j]=(power of j -1)-(i-1-gr[j]). Could you explain it? Thanks a lot.
•  9 years ago, # ^ |   0 We want to find number of men after j who are weaker. We know number of men before j , and we know number of stronger men before j , so we can easily find number of weaker men standing before j. As we know number of all men who are weaker than j , we can find number of those who are weaker and are placed after j with a subtracting what we just found.
•  9 years ago, # ^ |   0 Anyway , this doesn't decrease the time complexity
•  9 years ago, # ^ |   +1 I understand it now. Thanks very much, aryobarzan.
 9 years ago, # |   +1 Is implementation of segement tree really tough?
•  9 years ago, # ^ |   +2 No. It's not hard to implement it.Here's my own CPP struct for it:
•  9 years ago, # ^ |   +1 Thanx. It more or less look like "familiar" Binary Search.
•  9 years ago, # ^ |   0 yes ive seen your structure ... since im new on it ... Can u give me a sample implementation of the structure. And some problems to try.  thanx in advance
•  9 years ago, # ^ |   +1 See this as a direct sample of using a segment-tree. Also you can see the solutions of others there.
•  9 years ago, # ^ |   0 You can find some other problems here: And here's a classification for a lot of problems:
•  9 years ago, # ^ |   +1 thanx EKG and aryobarzan :D
 9 years ago, # |   +1 can anyone clearly explain how to do this using BIT ?
•  5 months ago, # ^ |   -8 BIT implementationExplanation:Let's try to solve a simpler version of the problem. Let's say, we have to find the number of inversions. That is, we have $a_1,a_2,a_3,...,a_n$. Then, we want to find out the pairs $a_i>a_j$ such that $ia_j>a_k$, such that $i>j>k$. We already have done a part of this. We can have another BIT that saves the number of inversions for each element as we're going from n to 1 in the loop. This information can be used to query the number of inversions that are present after the current number, for the numbers having a magnitude smaller than the current number. So, the loop looks like: for(int i=n;i>0;i--) { ans+=(arrF[i]==1?0:query(arrF[i]-1,BITZ)) ; int val = (arrF[i]==1?0:query(arrF[i]-1,BITS)) ; update(arrF[i],val,BITZ) ; update(arrF[i],1,BITS) ; } Where ans is the correct answer.BITS is the BIT that stores presence of elements. BITZ stores the number of inversions for the elements. You can use segment trees too here, if you change the BIT's implementation by a segment tree's one. But that isn't really necessary here I think.
•  2 months ago, # ^ |   0 I did it using BIT. 83312596. The idea is simple and is mentioned with the code itself.
 » 7 years ago, # |   +5 Can this be done using merge sort ...like inverse counting problem?
•  » » 7 years ago, # ^ |   0 Yes. For each index i, you can first find number of all inversions that have i as their first element and then all those that have i as their second element. Then just multiply them to find number of three-inversions (j,i,k) with i as their middle element.
•  » » » 3 months ago, # ^ |   0 well, why do you have to multiply? what about building two arrays: inv1, where inv1[i] — number of j < i such that a[j] > a[i] and inv2, where inv2[i] — number of j > i such that a[j] > a[i]. If I am wrong, could you please expand the idea of multiplying?
 » 3 years ago, # |   0 What is the meaning of this line "we add the segment [0,x-1] to our segment tree".An example would be very helpful.
 » 3 years ago, # |   0 my solution using merge sort algo to find inversions. http://codeforces.com/contest/61/submission/33820916
•  » » 2 years ago, # ^ |   0 For the second time of inversion counting, I got the gist of what you are doing, namely, finding for each element, the number of inversions in which it is occurring as the first element. Please can you elaborate more on the thought process behind the processing you have done before you invoke the inversion count the second time?
 » 2 years ago, # |   -8 In the year 2018, we have new-age technology that makes this problem fairly trivial to solve: Policy-based data structures. Specifically, order statistics trees. We can query them directly to find the number of elements less than x. So none of that coordinate compression/segment tree nonsense needed! See my solution here: http://codeforces.com/contest/61/submission/40569977See here for more information regarding the data structure: https://codeforces.com/blog/entry/11080
•  » » 3 months ago, # ^ |   0 wow
 » 13 months ago, # | ← Rev. 2 →   +5 for more explanation on this problem "sorry for my bad English :) " : First we should change the numbers as the tutorial says because 1e9 is too big, and we have only n elements and the element is distinct so we should assign to each number a new number, how we can do that without change the relation between powers of soldiers simply we can sort the elements and save the old index(we can do that by taking an array of pairs the first is the real power and the second is the index and sort this array). the problem says that we should take three indices, so we loop through the middle one in O(n) and now we should find how many element before him and bigger than him and how many elements after him and less than him let's take in the first how many elements after him and less than him, this can be done by the following way(we store the results on _right[MAX]): take a segment tree in each node in the segment tree we store how many elements below it the segment is empty in the first, but we know that the first element is the smallest so nothing is less than him so we add it to the segment using update function(it is very simple we add 1 in the location of the element, the location is the index before sort)now we loop through the elements of the sorted array and every time we find how the res by getting the numbers of elements to exist in the range [id + 1, n] (id is the index before sort)and after we find the result we add that element using the update functionhow does this work? because when we sort the array and work from small to big, so we are sure that if there is an element in the range [id+1,n] then the element in it is less than the current number. now let's find how many elements before him and greater than him, the idea is like the previous one(we store the results on _left[MAX]): we clear the segment tree using memset so all nodes now zero because no element is added until now.reverse the array because now we should find the greater elements now we also know that the first element is the greatest so nothing is greater than him so we add him using the same update function in the previous method.we loop also through elements and now the only difference is that the query should be in the range [1,id-1] and also id is the index before sort.now after finish the loop we reverse the _left array, why we do that? because as we know the final result is the summation of the _right[i]*_left[i];so if we don't reverse the _left array then the indices are reversing so we should find the summation of the _left[n-i+1] * _right[i];sure we can do that instead of reverse it. my code: https://ideone.com/sG31aS if you still don't understand please ask :)
 » 5 months ago, # |   0 If solving this problem with a segment tree is tough, I would suggest this easier version:For a permutation $a[1],\ldots, a[n]$ of $1,\ldots, n$ find the number of inversions using a segment tree: i.e., the number of pairs $ia[j]$.Here the segment tree can be built from an array $s[]$ where $s[k]= 1$ or $s[k]=0$ means that the number $k$ was seen, or not seen, respectively. Then we may traverse $a$ backwards: the number of inversions which begin at element $a[i]$ equals the number of elements less than $a[i]$ which have already been seen; this is the query of our segment tree from $1$ to $a[i]-1$. Then we update $s[a[i]]=1$, and continue.