Блог пользователя harsh-apcr

A Simple Counting Problem
Автор harsh-apcr, история, 6 месяцев назад, По-английски

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

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
6 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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://codeforces.me/blog/entry/57292

→ Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What is the idea tho?

    → Ответить
    • »
      »
      »
      6 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        6 месяцев назад, # ^ |
        ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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

        → Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
6 месяцев назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

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;
→ Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить
»
6 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

WRONG

→ Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
6 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    6 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
6 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить