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.
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:
Usual lower_bound won't work here. Please note, my operator definition of
< operator. I want both the .first and .second of pair to be less than the other.Lower bound will just check them based on .first and if they are equal, then only check for the .second.
Example:- $$$a=[(0,0),(1,2),(2,1)]$$$
I want
lower_bound({2,1})to return 1, but instead as per your solution it will return 2.Also, how can we use merge-Sort tree in case of pairs ? Please provide link for Task 1 is you saw it somewhere.
Your definition to operator < do not allow us to do a proper sort on the array, so I think it'll be difficulty to find an efficient solution.
Ex:
The first task is true 3D (offline) query. there is nothing better than except one of the many $$$O(n log^2 n)$$$ solutions. See https://oi-wiki.org/misc/cdq-divide/ and https://www.luogu.com.cn/problem/P3810. I hope you can read chinese.
Second task is very close to a full 3D query, I don't think it is realistic to expect anything simpler except n log^2 n.
The third task is a 2D query, simple sweepline + any choice of log DS will do in n log n .
Thanks a lot! Never knew about this website, before you mentioned.
For Task 2 I was wondering if we could do something like this:
Apply coordinate compression on the first element of pairs (for using them as index).
Create a mergeSort-tree initialized to $$$-\infty$$$
While iterating through the array:
update(pair.first[index],pair.second[value])Query for number of elements whose value > pair.second in the range [0,pair.first-1]
But updating and querying requires $$$O(\log^2 n)$$$ in a mergeSort-tree.
Can this be optimized to $$$O(logn)$$$? Using fractional cascading and some pre-processing maybe?
what I stated was inaccurate, in fact, your second task is exactly a 3D offline query ( given triples (i,j,k), calculate how many pairs satisfy $$$i_1 \lt i_2$$$, $$$j_1 \gt j_2$$$, $$$k_1 \gt k_2$$$.)
So I highly doubt there is a solution faster than $$$O(\log^2 n)$$$ on average, (given how well known this is in China).
what you described is one of the standard realistaion of a fully online 2D data structure (supporting add 2D point, and range sum query for 2D rectangle), it is highly unlikely that this can be optimised to $$$O(\log n)$$$ for this reason.
can fractional cascading be applied? defintely not directly (for reasons including it does not make sense unless it is a completely sorted array). But, I am not good enough to conclude that it is impossible, because it is possible that is some magical $$$O(n log n)$$$ solution out there (I did a quick search and it seems that this is an open problem) -- the world is waiting on anyone that can confirm or deny this.
just out of curiosity what do you mean by 2D , 3D stuff ? why did u call sweepline 2D ?
the general DS/solution to a k-dimensinoal query is $$$O(n log^k n)$$$.
In the special case that our queries are offline, then we can reduce dimension by one, using sort+ sweepline and use an online solution for it. So an offline 2D query = sweepline plus any online 1D structure is $$$O(n \log n)$$$. The general 2D data structures, including BBST (ordered set) on segment tree, or 2DBIT, supporting online queries, are all $$$O(n \log^2 n$$$).
Wavelet tree, persistent segment tree or merge sort tree (with fractional cascading) are special cases (all $$$O(n \log n)$$$.) that can handle queries (l,r,v): count how many A[i] >= v for i in [l,r] if there are no update queries, (so, partially offline). This is weaker than the general full 2D online queries.
oh i see , this generalizes stuff and makes it alot easier
could u give a general idea on how to solve any k dimensional query in nlog^kn online ?
like given a 4D query how would u do it in nlog^4n ? make a segment inside a segment inside a segment 3 times ? or how would u generalize a solution to any k dimensional query ?
Yes, nesting (implicit) segment trees seems to be the best option.
The final one could be a BBST to save memory, giving a memory requirement of $$$O(n log^{k-1} n)$$$.
If the overall set-up is offline, generally, you can use one extra layer of cdq to remove one dimension ( so still $$$O(n log^k n)$$$ but easier to code and better constant factor).
Of course, it is unlikely that you get anything practically better than the $$$O(n^2)$$$ for 5 dimensions or higher (4 dimensions already questionable).
nice , i would always waste 20-30 minutes trying to optimize this approach but never happens pretty much in every queries problem i would take over 20 minutes to reach this row form of answering it then start look for observation to maybe optimize and stuff , just knowing that i cant achieve better than nlog^k n complexity saves alot of wrong directions i would be taking during a thought process , not sure if u got the time , but i would love to read a whole blog about query handling , general observations and how u approach them in general
I think task 1 can be solve using offline queries or persistent segment tree for online.