CF_contest_practice_2's blog

[Segment Tree?] Count the number of pairs in a range less than a given pair.
By CF_contest_practice_2, 4 hours ago, In English

Given an array of pairs $$$p[]$$$ of length $$$n(\leq 100000)$$$ I want to do the following:

Task 1: Given $$$q(\leq 100000)$$$ queries and $$$L,R,(pair\ p)$$$, output the number of pairs < p in the range $$$[L,R]$$$.

Task 2: Count the number of inversions in it. I can do inversions += query(i+1,n,p[i]) (if answer to Task 1 is available).

Task 3: Same as Task 1, but $$$L=1,R=n$$$ always. Can we directly use lower_bound for pairs < operator somehow?

< operator for pairs is defined as follows:- < (p1,p2){ return p1.F<p2.F && p1.S<p2.S;}

I know that we can do Task 1 for integers using a mergeSort-Tree, but how to do it for pairs?

Please let me know if there is an easier solution for Task 2 or Task 3 separately having an easier/direct implementation or smaller Time Complexity.

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

»
23 minutes ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Pretty sure that task 1 can be solved using merge sort tree.

You can also use lower_bound function normally if you have an array of pairs:

pair<int,int> a[n], x;
lower_bound(a, a+n, x);
→ Reply