Contest de seleccion IOI 2022: B. Interseccion Interna

Problem Statement: Given \(m\) segments between \(n\) points in a circle, determine how many segments intersect.

There are at least two ways to think about this problem: open/close parentheses and intervals. In both representations, we can see that we would like to count the number of open parentheses or intervals (i.e. open events) when we are faced with a close parentheses or intervals. For interval, this problem is known as Problem: Count number of interval intersections. From the problem constraints, it is clear that we need something better than linear time.

RB 2022-06-16 10.54.43 1.jpg

Let's use the interval representation for now on. Suppose that we are processing all events from left to right: open \((1, 3)\), open \((1, 5)\), open \((2, 4)\), open \((2, 5)\), close \((1, 3)\), …

Be \(c\) an array where \(c[i]\) is the number of open events minus the number of close events that happened on the \(i\)th position. The sum of \(c[1]+c[2]+..+c[i]\) represents the number of open intervals that start on \(1..i\) but closes on \(i..n\). For each event, we can update \(c\) as following: (1) an open event \((l, r)\) adds one to \(c[l]\) and subtracts one from \(c[r]\), and (2) an close event \((l, r)\) subtracts one from \(c[l]\) and adds one to \(c[r]\). To check the number of intersection on a close event \((l, r)\), we can compute \(c[l]+c[l+1]+..+c[r]\). We can use a FenwickTree to implement \(c\) and do the operations add and sum in logarithmic time. The following code implements this idea.

Time complexity: \(O(n\lg n)\).
Space complexity: \(O(n)\).

#include <algorithm>
#include <iostream>
#include <set>
#include <string.h>
#include <vector>
#include <stack>
#include <assert.h>

using namespace std;

#define ll long long

// source: https://cp-algorithms.com/data_structures/fenwick.html#finding-sum-in-one-dimensional-array
struct FenwickTree {
    vector<ll> bit;  // binary indexed tree
    int n;

    FenwickTree(int n) {
        this->n = n;
        bit.assign(n, 0);
    }

    FenwickTree(vector<ll> a) : FenwickTree(a.size()) {
        for (size_t i = 0; i < a.size(); i++)
            add(i, a[i]);
    }

    ll sum(int r) {
        ll ret = 0;
        for (; r >= 0; r = (r & (r + 1)) - 1)
            ret += bit[r];
        return ret;
    }

    ll sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }

    void add(int idx, int delta) {
        for (; idx < n; idx = idx | (idx + 1))
            bit[idx] += delta;
    }
};

ll solve(int n, vector<pair<int, int>> points) {
  FenwickTree ft = FenwickTree(n + 1);
  ll ans = 0;
  for (vector<pair<int, int>>::iterator it = points.begin(); it != points.end(); it++) {
    int l = it->first;
    int r = it->second;
    if (l < r) {
      ft.add(l, +1);
      ft.add(r, -1);
    } else {
      ft.add(r, -1);
      ft.add(l, +1);
      ans += ft.sum(r + 1, l);
    }
  }
  return ans;
}

int main() {
  int n, m;
  vector<pair<int, int>> points;
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int l, r;
    cin >> l >> r;
    points.push_back(make_pair(l, r));
    points.push_back(make_pair(r, l));
  }
  sort(points.begin(), points.end());
  cout << solve(n, points) << endl;
  return 0;
}