Для данного массива подсчитывайте комбинации из трех элементов в порядке убывания

Question

Я решаю одну проблему из прошлых соревнований по программированию, поэтому мне нужна помощь, я объясню проблему в одном предложении. У вас есть массив размером N, где N может достигать 10^5. А затем во второй строке у вас ровно N элементов. Итак, теперь вам нужно подсчитать способы выбора трех элементов из массива, чтобы они были в порядке убывания. Вот пример

N = 4 и массив выглядит так: 190, 180, 170, 168. У нас есть ровно четыре способа выбрать эти три элемента. 1. (190, 180, 170) 2. (190, 180, 168) 3. (190, 170, 168) и 4. (180, 170, 168)

Я думаю, что это необходимо решить с помощью дерева сегментов, Не знаю, с каким аргументом я должен создать дерево. Заранее спасибо.

Answer 1

1. Мы можем предположить, что все числа в диапазоне [0, n - 1] (в противном случае, мы можем «компресс» их).

2. Зафиксируем положение среднего элемента в тройке. Теперь мы можем подсчитать количество больших элементов слева от него и умножить на число меньших элементов справа от него.

3. Как подсчитать количество больших элементов с меньшими индексами? Вот псевдо-код, который объясняет:

   tree = SegmentTree(0, n - 1) // for sum and add operations 
   for i = 0 ... n - 1 
       greaterLeft[i] = tree.getSum(a[i] + 1, n - 1) 
       tree.update(a[i], 1) 
   

4. Обратите внимание, что нам нужно обновления в точке и сумма ряда. Дерево двоичных индексов может сделать это эффективно (его легче реализовать, чем дерево сегментов).