harsh-apcr's blog

A Simple Counting Problem
By harsh-apcr, history, 2 years ago, In English

You're given a list of points $$$(x_1, y_1), \ldots, (x_n, y_n)$$$

There are two kinds of queries (there are $$$q$$$ queries, where $$$1\leq q \leq 10^5$$$)

  1. Insert a new point in this list
  2. Given $$$(x, y)$$$ and you need to count number of points in the given list with $$$x_i \leq x$$$ and $$$y_i \leq y$$$

you can expect the constraints to be $$$n \leq 10^5$$$ and $$$0 \leq x_i, y_i, x, y \leq 10^9$$$

Any help is appreciated, Thanks

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

Comments Comments (15)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

Implicit 2d fenwick tree should be enough I guess These requests are just +1 in point and sum on prefix 

unordered_map<int, unordered_map<int, int>> t; // or smth like that

int get(int x, int y) {
    int res = 0;
    for (int i = x; i > 0; i -= i & -i)
        for (int j = y; j > 0; j -= j & -j)
            res += t[i][j];
    return res;
}

void add(int x, int y, int v) {
    for (int i = x; i <= MAX; i += i & -i)
        for (int j = y; j <= MAX; j += j & -j)
            t[i][j] += v;
}

will be almost the whole code. Not sure where you can read about it, the first blog i found: https://mirror.codeforces.com/blog/entry/57292

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    What is the idea tho?

    → Reply
    • »
      »
      »
      2 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      Just solving directly with existing algorithms

      With fenwick tree we can answer requests "add value in point" and "get sum on prefix" in $$$log(MAX)^d$$$ where d is the number of dimensions in prefix sum, which is actually this task.

      Like the same if we build a standart 2d prefix sum and for each "insert point" request we would fully rebuild it.

      → Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I almost used dynamic segment trees not knowing there is a much easier solution.

    → Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it -9 Vote: I do not like it

My bad lol

→ Reply
  • »
    »
    2 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    This easily fails with points like: {0,0}, {2,2}, {3,1}, where the answer for both {2,2} and {3,1} is 1, whereas your code returns 2 distinct answers. However, this idea can be extended, first by finding all x <= current_x and after that all y <= current_y using multisets with keys x and y respectfully, and finding their intersection

    → Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

WRONG

→ Reply
»
2 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

An obvious idea is to make 2 multisets of points, one sorted by $$$x$$$ and another by $$$y$$$. For each 2nd type query we find the intersection of multisets, one of which has points which satisfie $$$x_i \le x$$$, and the second $$$y_i \le y$$$, both of which can be computed in $$$O(log(n))$$$. However, this depends on the intersection finding time complexity, which is unknown for me.

Time complexity for each query is $$$O(log(n)*F(s,d))$$$, where $$$F(s,d)$$$ is time needed to compute the intersection of multisets $$$s$$$ and $$$d$$$

Hope this helps

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

This problem (statement only in Romanian) is very simmilar. You are asked for multiple values to compute how many values to the left and above are equal to that value and sum these counts. The solution is in $$$O(N^2 \cdot \log N)$$$ using the same idea sugested by others.

→ Reply
»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I didn't think much, but you should be able to modify the first example problem from here to solve your problem offline.

→ Reply