Базова идея

Нека отварящите скоби са +1 и затварящите са -1. Тогава низа е валиден, когато сумата на всеки рпефикс е неотрицателна. Също е нужно и сумата на целяи да е 0, но това винаги ще важи.

Един събстринг може да бъде обърнат тогава и само тогава, когато след префиксната сума до преди началото му е >= от - минималната суфиксна сума на събстринга.

Ще трансформираме това в следното:

Един събстринг може да бъде обърнат тогава и само тогава, когато след префиксната сума до преди началото му е >= от префиксната сума до края му - максималната префиксна сума между двата му края.

Т.е. нека prefSum[i] = sum_{0 <= j < i} a[j].
Събстринг [l, r) може да бъде обърнат ако:

prefSum[l] >= prefSum[r] - max_{l <= i <= r} prefSum[i]

(Забележете, че <= за i могат да са и <, тъй като крайните случаи никога не са лимитиращи.)

Сега вече работим само с префиксни суми, които можем да прекомпютнем и от там да се опитваме да решим задачата.

Решение за N^2

За N^2 или по бавни решения можем да правим това много лесно, като просто пробваме всеки l и после движим r и следим макс префиксната сума.

Решение за N log^2

Има две различни валидни идеи.

Разделяй и владей

В една итерация на DnC имаме L < R и M = (L + R) / 2, т.е. L <= M < R. Искаме да преброим всички валидни двойки l, r, такива че L <= l <= M < r <= R.
И после ще пуснем DnC(L, M) и DnC(M + 1, R).

Можем да видим, че prefSum[l] >= prefSum[r] - max_{l <= i <= r} prefSum[i] е вярно, когато са верни следните две:
1. prefSum[l] >= prefSum[r] - max_{l <= i <= M} prefSum[i]
2. prefSum[l] >= prefSum[r] - max_{M < i <= r} prefSum[i]

Заебележете, че най десния член в двете е функция само на l в 1. и функция само на r в 2. Това ни навежда на една от две идеи:
1. Да "филтрираме" двойките първо по 1. и после по 2. (или обратното).
2. Да разделим двойките на база дали 1. или 2. ще е по лимитиращо и да решим всяка група поотделно (изисква да забележим, че границата за r където се сменя това се движи монотонно с l.)

И в двата подхода ползваме няколко пъти някакви движещи се пойнтъри и Фенуик. Потенциално може и да сортираме някакви стойности. Имаме N log работа в една итерация на рекурсията, та общо DnC-то излиза N log^2.

Разгледайте примерните решения n1log2_nasko и n1log2_opt за детайли за идеи с 1. и с 2. съответно. 2. се оказва доста по бързо и добре написано може да мине и за следващия събтаск.

Декартово дърво и small to large

Другия тип подод е да построим Декартово дърво, т.е.:
1. Намираме максимум стойността в текущия рейндж.
2. Правим я корен на текущото (под)дърво.
3. Разделяме рейнджа на две около нея.
4. Рекурсивно строим поддървета в двете части и правим корените им децата на нашия корен.

Сега за всеки връх M ще разглеждаме двойки l, r, такива че l идва от лявото поддърво, а r -- от дясното. Забележете, че за разлика от с DnC решението тук max prefSum е точно M по конструкция на Декартовото дърво. Проблемът е, че може то да не е балансирано та ще ползваме small to large. Т.е. ако лявото поддърво е по-малко, ще итерриаме през l и за всяко ще създаваме заявки за подходящи r, а иначе наобратно. Куеритата са от тип "колко елемента със стойност под/над X има в даден рейндж".

После можем да си сортираме заявките (в линейно време, с count sort) по стойността за която ще куериваме и да итерираме през тях и самите елементи заедно. При ъпдейт за елемент, добавяме 1 към неговата позиция във Фенуик, а при куери просто искаме сумата в рейнджа.

Общо имаме N log заявки и всяка отнема log, т.е. общо излиза N log^2.

Разгледайте n1log2_koynov и n1log2_mihov_opt за детайли (второто е доста оптимизирано написано и на ръба минава и за следващия събтаск).

Решение за N log

И при двата подхода (и вариант 2. на DnC, и "правилно" структурирано решение с Декартово) можем да видим, че всъщност навсякъде всички ъпдейти са или с +1 или с -1 от предния (защото поредните позиции имат и съседни prefSum-и) и същото важи и за заявките. Т.е. вместо Фенуик можем да следим просто текущ отговор и текущо активно "куери". После при всеки ъпдейт адваме към текущия отговор, ако то е под (или над, спрямо какво точно куериваме) текущото куери; също нанасяме и ъпдейта и върху масив на съответнатап озиция. После, при всяко куери -- то или се вдига с 1 или пада с 1, ъпдейтваме текущия отговор или с + или с - съответната позиция.

Така махаме log-а от Фенуика и и двете решения остават N log.

Може да видите n1log или n1log_koynov за детайли (първото с DnC, второто с Декартово).

Решение за "под" N log

Това решение е доста специфично. Сложността му, също. Тя е o(N log N) (а не O(N log N)). Това значи, че произволни сложности стриктно под N log са постижими от тестове (но всъщност с все по лоши константи, колкото по близо до N log N), но чак N log не е. Важното е, че емпирично в най лошия случай се държи като 4-5 * N за дадените ограничения.

Основните идеи на решението са 3:

1. Групи/Чънкове

Ще движим пойнтър за l от дясно наляво и ще държим всички преминати позиции (възможни r) в групи от последователни позиции.

За дадена група, нейната максимална стойност (на prefSum) ще е най-лявата ѝ точка. Също така максималната ѝ стойност трябва да е стрикнто по малка от тази на следващата група.

За всеки отрицателен офсет от тази максимална стойност, ще държим броя позиции в групата, които имат такава prefSum стойност. Това ще стане като пазим тези бройки във вектор наобратно (т.е. последната стойност е бройката с офсет 0, предпоследната с офсет -1 и т.н.).

Когато придвижим l наляво, или получаваме по-ниска стойност, при което просто създаваме нова единична група, или получаваме по висока стойност. Тогава първо пушваме 1 накрая на вектора на текущата (най-лява) група. После гледаме дали тя трябва да се мърджне със следващата (винаги ще трябва освен ако не е последна). Тогава премахваме по-малката група и добавяме нейните стойности към по-голямата като просто итерираме през тях (small to large).

Цялото това следене очевидно е макс O(N log N) заради small to large-а. Но всъщност, можем да видим, че цената на мърджа (и самия размер на групите) е пропорционален на броя различни стойности в тях, а не на броя елементи (ако напишем кода по такъв начин). Т.е. ако ги разгледаме в Декартово дърво small to large мърджа е на база дълбочината на по-плиткото поддърво. Известно е (и лесно за доказване), че тогава общата цена е O(N).

2. Архив

Ние ще искаме в част 3. да итерираме през всички групи и да събираме някакви стойности. Проблемът е, че лесно можем да имаме твърде много групи. Затова ще проверяваме, всеки път когато създадем или модифицираме някоя група, след колко итерации (ако някога) тя ще бъде модифицирана пак (това може да стане с лесен прекомпют). Ако ще бъде модифицирана след по-малко итерации от размера ѝ, тогава я оставяме да си стои. Иначе обаче, итерираме през стойностите ѝ добавяме бройките им в глобален count масив индексиран по стойности на prefSum (като офсети). Идеята е, че това не оставя да има твърде много активни (неархивирани) групи, а за всички останали имаме нужните суми в архива.

Важно е, че когато ше мърджваме 2 групи, ако дясната е архивирана, ще я деархивираме, ще ги мърджнем и после пак (потенциално, ако е изпълнено условието) ще архивираме мърджнатата. Можем, като оптимизация да деаривираме дясната само ако общата няма да бъде архивирана (а иначе да архивираме само лявата преди мърджа).

Сега можем да сметнем цената на архивациите като видим, че всеки елемент можем да архивираме веднъж и да остане така, а преди това имаме потенциално много архивация-деархивация двойки. Но те се случват само при мърджване, т.е. г/д можем да ги броим като част от мърджовете и да излязат от small to large отново (защото лявата група трябва да е с дължина поне размера на дясната, която бива деархивирана), т.е. очевидно е до O(N log N), но отново е до O(N) (малко по-сложно доказателство, тъй като може лявата да има по-малко стойности, но по голяма дължина; но пак излиза).

3. Куерита

За текущото l просто искаме да знаем колко възможни r има, които образуват валиден събстринг за обръщане. Ами ако r е в дадена група, то просто трябва да е на отрицателен офсет <= prefSum[l]. Т.е. можем наивно да итерираме през всички групи и всички офсети до prefSum[l] и да съберем бройките.

Вместо да итерираме до prefSum[l], отново ползваме трика че всички куерита са на +1 или -1 от предното, та просто следим тази сума и вадим/прибавяме каквото е нужно от всяка група (на точно една позиция). Също виждаме, че и при ъпдейт (пушване на 0) е нужно да аксеснем само О(1) позиции в писъка бройки на текущата модифицирана група.

Забележете, че всъщност ще итерираме само през неархивираните групи, а сумата от останалтие на даден офсет ще вземем от архива.

Тази част има сложност О(N * среден брой неархивирани групи). Лесно се вижда, че никога няма повече от log неархивирани групи, защото всяка неархивирана група е с размер >= сумата на всички леви (неархивирани) групи. Та това би дало граница от O(N log N).

Но всъщност, в примерите които генерират log групи в даден момент, в голямата част от "времето" имат много по малко от log групи. Т.е. 1 (първата) група е активна в N / 2 позиции, втората в N / 4 и т.н. Но общо това е цена от N.

Всъщност при всяка такава геометрична прогресия на размери на групи (като брой стойности и дължина) получаваме линейна обща цена.

В най лошия случай примера изглежда като:
1. Създаваме долина K надолу и K нагоре.
2. Останалите N - K позиции разделяме на групи с дължина K.
3. Всяка група генерираме рекурсивно, така че след нея да се върнем на същата височина, за да "рефрешнем" тази първа група.

Ако анализираме цената която това дава спрямо каква функция на N е K. Получаваме линейна цена за K линейна функция на N. За K съблинейна функция на N, можем да игнорираме "загубата" на позиции от 1. и да кажем че:

T(N) <= N + T(K(N)) * N / K(N)

Но за всяка съблинейна функция K(N), това е стриктно под N log N. Също така когато K расте твърде близо до линейно, константата става ужасна. Та на практика в най-лошия случай имаме нешо като K = sqrt(N) и тогава получаваме нещо като 4-5 N като обща цена.

Разгледайте n1log_sub или n1log_sub_encho за имплементации.