Оцінка#11806

Оцінка (Розбір)

Автор проблеми:	Хасан Салех (MathModel)
Підготовлено:	Хасан Салех (MathModel)
Редакція:	Хасан Салех (MathModel)

Просте рішення полягає в тому, щоб пройти через усі підсегменти в масиві та підсумувати оцінки, що дає рішення $O (n^{2})$ \mathcal{O}(n^2). Однак це занадто повільно; нам потрібно зробити це швидше.

Щоб прискорити обчислення, нам потрібно обчислити для кожного підсегмента, що закінчується на індексі $i$ , скільки з них є чудовими, скільки ідеальними, і скільки звичайними.

Нехай $s$ буде сумою масиву. Ми можемо легко визначити, чи є сума підсегмента більшою за $\frac{s}{2}$ \frac{s}{2}, тоді він буде чудовим; якщо менше за $\frac{s}{2}$ \frac{s}{2}, він буде звичайним, а якщо $s$ парне і сума підсегмента дорівнює $\frac{s}{2}$ \frac{s}{2}, він буде ідеальним.

Таким чином, нам потрібно отримати префіксну суму для кожного індексу $p_{i}$ p_i та підрахувати кількість сегментів, які більші, рівні або менші за $p_{i} - \frac{s}{2}$ p_i - \frac{s}{2}. Це можна зробити багатьма способами; один із способів - обчислити всі префіксні суми та відобразити їх на індекси від $1 - m$ 1-m, де $m$ - кількість різних префіксних сум. Тоді ми можемо використовувати сегментне дерево або дерево Фенвіка разом з бінарним пошуком, щоб вирішити цю задачу. Це зробить часову складність $O (n lo g n)$ \mathcal{O}(n \log n), що достатньо швидко для вирішення цієї задачі за допомогою Python.

import bisect
class fenwick(object):
    def __init__(self, n):
        self.n = n
        self.cul = [0]*n
        self.maxd = len(bin(n))-3

    def update(self,index,diff):
        i = index
        while i<self.n:
            self.cul[i] += diff
            i += (i+1)&(-i-1)


    def getaccu(self,index):
        output = 0
        i = index
        while i>=0:
            output += self.cul[i]
            i -= (i+1)&(-i-1)
        return output

def solve():
    n = int(input())
    arr = list(map(int,input().split()))
    tot = sum(arr)
    nums = [0]
    for num in arr:
        nums.append(nums[-1]+num)
    nums = sorted(list(set(nums)))
    nums = [-float('inf')] + nums 
    mapping = {}
    already = {}
    already[0] = 1
    for i in range(len(nums)):
        mapping[nums[i]] = i
    fen = fenwick(len(nums)+1)
    fen.update(mapping[0],1) 
    count = 0
    accu = 0
    ans = 0
    for i,num in enumerate(arr):
        accu += num
        target = accu + (-tot) // 2
        loc = bisect.bisect(nums, target) - 1
        good = fen.getaccu(loc)
        ans += good * 2
        ans -= i + 1 - good
        if tot % 2 == 0 and target in already:
            ans += already[target]
        fen.update(mapping[accu],1)
        if accu not in already:  already[accu] = 0
        already[accu] += 1
    print(ans)

for _ in range(int(input())):
    solve()

Python