Порахуйте трійки#9022

Порахуйте трійки (Розбір)

Відсортуємо всі три масиви. Для кожного елемента $b_{j}$ b_j за допомогою бінарного пошуку визначимо:

кількість елементів $x$ в масиві $a$ , які менші $b_{j}$ b_j,
кількість елементів $y$ в масиві $c$ , які більші $b_{j}$ b_j.

Тоді для фіксованого значення $b_{j}$ b_j існує рівно $x * y$ x * y трійок виду $(a_{i}, b_{j}, c_{k})$ (a_i, b_j, c_k), що задовольняють нерівність $a_{i} < b_{j} < c_{k}$ a_i < b_j < c_k.

Приклад

Розглянемо відсортовані масиви і обчислимо кількість підходящих трійок для $b_{5} = 10$ b_5 = 10.

Маємо: $a_{i} < b_{5}$ a_i < b_5 при $i \leq 5$ i \le 5, а $c_{k} > b_{5}$ c_k > b_5 при $k \geq 7$ k \ge 7.

Таким чином, нерівність $a_{i} < b_{5} < c_{k}$ a_i < b_5 < c_k виконується для $1 \leq i \leq 5$ 1 \le i \le 5 і $7 \leq k \leq 8$ 7 \le k \le 8.

Кількість трійок $(a_{i}, b_{5}, c_{k})$ (a_i, b_5, c_k) дорівнює $5 * 2 = 10$ 5 * 2 = 10.

Реалізація алгоритму

Оголосимо робочі масиви.

#define MAX 100000
int a[MAX], b[MAX], c[MAX];

Читаємо вхідні масиви.

scanf("%d", &n);
for (i = 0; i < n; i++) scanf("%d", &a[i]);
for (i = 0; i < n; i++) scanf("%d", &b[i]);
for (i = 0; i < n; i++) scanf("%d", &c[i]);

Сортуємо масиви.

sort(a, a + n);
sort(b, b + n);
sort(c, c + n);

Кількість шуканих трійок будемо підраховувати в змінній $r es$ . Перебираємо значення $b_{j}$ b_j.

res = 0;
for (j = 0; j < n; j++)
{

Кількість елементів масиву $a$ , менших $b_{j}$ b_j, дорівнює $x$ .

  x = lower_bound(a, a + n, b[j]) - a;

Кількість елементів масиву $c$ , більших $b_{j}$ b_j, дорівнює $y$ .

  y = n - (upper_bound(c, c + n, b[j]) - c);

Тоді для значення $b_{j}$ b_j існує рівно $x * y$ x * y шуканих трійок.

  res += x * y;
}

Виводимо відповідь.

printf("%lld\n", res);

Java реалізація

import java.util.*;

public class Main 
{
  static int lower_bound(int m[], int start, int end, int x)
  {
    while (start < end)
    {
      int mid = (start + end) / 2;
      if (x <= m[mid])
         end = mid;
      else
        start = mid + 1;
    }
    return start;
  }

  static int upper_bound(int m[], int start, int end, int x)
  {
    while (start < end)
    {
      int mid = (start + end) / 2;
      if (x >= m[mid])
        start = mid + 1;
      else
        end = mid;
    }
    return start;
  }

  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);    
    int i, n = con.nextInt();
    int a[] = new int[n];
    for(i = 0; i < n; i++) a[i] = con.nextInt();

    int b[] = new int[n];
    for(i = 0; i < n; i++) b[i] = con.nextInt();

    int c[] = new int[n];
    for(i = 0; i < n; i++) c[i] = con.nextInt();

    Arrays.sort(a); Arrays.sort(b); Arrays.sort(c);
    
    long res = 0;
    for (i = 0; i < n; i++)
    {
      int x = lower_bound(a, 0, n, b[i]);
      int y = n - (upper_bound(c, 0, n, b[i]));
      res += 1L * x * y;
    }
    
    System.out.println(res);
    con.close();
  }
}

Java