разделяй и властвуй, чтобы посчитать количество хороших сегментов

Question

Я какое-то время изучал «разделяй и властвуй» и сейчас изучаю следующую проблему:

Учитывая перестановку P длины N, посчитайте количество хороших сегментов. Обратите внимание, что последовательность A из N целых чисел называется перестановкой длины N, если:

1≤ A _i ≤ N для всех 1 ≤ i ≤ N и A _i ! = A _j для всех 1 ≤ i! = J ≤ N.

Непрерывный отрезок [l, r] перестановки P равен хорошо , еслизначение (P _l , P _{l + 1} , ..., P _r ) также является непрерывным. То есть, если мы соберем P _l , P _{l + 1} , ..., P _r в новый список B и отсортируем его, то это будетудерживать:

B ₁ = B ₂ -1, B ₂ = B ₃ -1, .. ., B _i-1 = B _i -1, ..., B _{| B | −1} = B _{| B |} -1.

Например, в перестановке [3, 2, 4, 5] есть 8 хороших сегментов:

[3], [2], [4],[5], [3,2], [4,5], [3,2,4] и [3,2,4,5]

Я проанализировал несколько случаев при объединении двухмаленькие разделенные массивы, но я не могу придумать стратегию, которая может обнаружить хорошие сегменты, которые пересекают два отдельных массива за O (N) времени.

Как это можно сделать?

Answer 1

Лично я не думаю, что здесь можно эффективно применять принцип «разделяй и властвуй».

Вам необходимо проверить O(n^2) подстрок заданной перестановки. Вы можете применить метод «разделяй и властвуй», например, разделив массив на 2 половины (левую и правую), осмотрев все подстроки, начиная с левой и заканчивая правой, а затем рекурсивно вызывая левую и правую половинки. Это даст:

n/2 * n/2 = (n/2)^2 = (n^2)/4 подстрок на уровне 1

n/4 * n/4 + n/4 * n/4 = 2 * (n/4)^2 = (n^2)/8 подстрок на уровне 2

n/8 * n/8 + n/8 * n/8 + n/8 * n/8 + n/8 * n/8 = 4 * (n/8)^2 = (n^2)/16 подстрок на уровне 3 и т. Д.

Это асимптотически дает O(n^2 * log n) подстрок для анализа, хуже, чем O(n^2) подстрок, если мы просто обрабатываем их итеративно

Для числа подзадач, больших 2, дела обстоят не лучше: если мыразделить на 3, сложность составляет O(n^2 * log3n) и т. д.