Bal#11806

Bal (Həll təhlili)

Problem Müəllifi:	Hasan Saleh (MathModel)
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə:	Hasan Saleh (MathModel)

Sadə bir həll yolu, massivdəki bütün alt seqmentləri dövr etmək və balları toplamaqdır ki, bu da $O (n^{2})$ \mathcal{O}(n^2) həlli verir. Lakin, bu çox yavaşdır; biz bunu daha sürətli etməliyik.

Hesablama sürətini artırmaq üçün, $i$ indeksində bitən hər bir alt seqment üçün, onların nə qədərinin möhtəşəm, nə qədərinin mükəmməl və nə qədərinin normal olduğunu hesablamaq lazımdır.

$s$ massivinin cəmi olsun. Alt seqmentin cəminin $\frac{s}{2}$ \frac{s}{2}-dən böyük olub olmadığını asanlıqla müəyyən edə bilərik, əgər böyükdürsə, o, möhtəşəm olacaq; əgər kiçikdirsə, o, normal olacaq, və əgər $s$ cütdürsə və alt seqmentin cəmi $\frac{s}{2}$ \frac{s}{2}-yə bərabərdirsə, o, mükəmməl olacaq.

Beləliklə, hər indeks üçün prefiks cəmini $p_{i}$ p_i əldə etməliyik və $p_{i} - \frac{s}{2}$ p_i - \frac{s}{2}-dən böyük, bərabər və ya kiçik olan seqmentlərin sayını hesablamaq lazımdır. Bu bir çox yollarla edilə bilər; bir yol, bütün prefiks cəmlərini hesablamaq və onları $1 - m$ 1-m indekslərinə xəritələməkdir, burada $m$ fərqli prefiks cəmlərinin sayıdır. Sonra biz bu problemi həll etmək üçün seqment ağacı və ya Fenwick ağacı ilə birlikdə ikili axtarışdan istifadə edə bilərik. Bu, vaxt mürəkkəbliyini $O (n lo g n)$ \mathcal{O}(n \log n) edəcək ki, bu da Python ilə bunu həll etmək üçün kifayət qədər sürətlidir.

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