harsh-apcr's blog

A Simple Counting Problem
By harsh-apcr, history, 6 months 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

»
6 months ago, # |
  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
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is the idea tho?

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        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
      • »
        »
        »
        »
        6 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks, I actually had the same approach in mind but quickly dropped that idea due to the constraints on $$$x, y$$$. Using a map is a nice idea

        → Reply
  • »
    »
    6 months ago, # ^ |
      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
»
6 months ago, # |
  Vote: I like it -9 Vote: I do not like it

I think using an ordered_set might solve it because you can insert in O(logN) and search for the number of points smaller (x,y) with the function (order_of_key) also using O(logN) I think it might goes with smth like this where s is an ordered_set

cin >> op >> x >> y;
        if (op == 1)
            s.insert({x, y});
        else
            cout << s.order_of_key({x, y}) << endl;
→ Reply
  • »
    »
    6 months ago, # ^ |
      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
»
6 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

WRONG

→ Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think this will work because xi <= x and xi + yi<= x + y is not sufficient condition for xi <= x & yi <= y. e.g. for (3,7) & (10,6) here xi <= xi & xi + yi<= x + y both hold but yi <= y doesn't hold.

    → Reply
»
6 months ago, # |
← 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
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Intersection finding is linear in the sizes of two sets, so per query you'd be spending $$$O(n \log n)$$$ time.

    → Reply
    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So Overall $$$O(n*log(n)*q)$$$? I wonder if this works

      → Reply
»
6 months ago, # |
  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
»
6 months ago, # |
  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