TRIQUERY - Editorial

thank you.

One generally maps your range of 10^9 values to O(10^5) actual values. (Use a STL map or set or something). The mapping should only preserve ordering of elements.

For example, if your input (into your BST) was 5, 10, 10^7, then first make the mapping


5 -> 1
10 -> 2
10^7 -> 3

and use just these mapped values in your BIT.

2 Likes

I thought of this . but suppose we want to do online processing of queries .

offline mode means that you “don’t” calculate your answer of every input query separately but either you do some preprocesing before taking input or you take all the input and find answer to the all queries at the same time. [here same time means like you are going though the input queries and finding “half” answer to some queries and then coming back again and again]

1 Like

I have a problem here: -->“How do we find num(points left of B and below G)? The answer lies in the line L1. When our sweep-line was at L1, we have: Total number of points seen so far = points either left of B or below G.”<-- I think if L1 sweep means all the points below this line in the diagram then it is “not” equal to the “points on the left of B or below G” because there can be some point b/w L2 and L1 and on the left of B which are not covered by L1 sweep. same for b/w L2 and L1 and below G. please clarify. Please also clarify the definition of line-sweep.

got it. :slight_smile: For this part of problem (refer above comment), it is a completely new BIT which is calculated from points and queries sorted by their x coordinate. see Setter’s solution for clarification.

1 Like
1 Like

its idx&-idx the bitwise AND operation between idx and its negation

Thanx @sparshgunner12. I finally understood whats happening.