Ball#11806

Ball (Editorial)

Muammo muallifi:	Hasan Saleh (MathModel)
Tayyorlagan:	Hasan Saleh (MathModel)
Tahririy:	Hasan Saleh (MathModel)

Oddiy yechim - massivdagi barcha subsegmentlar bo'ylab o'tish va ballarni yig'ish, bu esa $O (n^{2})$ \mathcal{O}(n^2) yechimni beradi. Biroq, bu juda sekin; biz buni tezroq qilishimiz kerak.

Hisoblashni tezlashtirish uchun, har bir subsegment uchun, u $i$ indeksida tugasa, nechtasi ajoyib, nechtasi mukammal va nechtasi oddiy ekanligini hisoblashimiz kerak.

$s$ massivning yig'indisi bo'lsin. Biz subsegmentning yig'indisi $\frac{s}{2}$ \frac{s}{2} dan katta yoki kichikligini osonlik bilan aniqlay olamiz; agar katta bo'lsa, ajoyib; agar kichik bo'lsa, oddiy, va agar $s$ juft bo'lsa va subsegmentning yig'indisi $\frac{s}{2}$ \frac{s}{2} ga teng bo'lsa, mukammal bo'ladi.

Shunday qilib, har bir indeks uchun prefiks yig'indisini $p_{i}$ p_i olishimiz kerak va $p_{i} - \frac{s}{2}$ p_i - \frac{s}{2} dan katta, teng yoki kichik bo'lgan segmentlar sonini hisoblashimiz kerak. Buni ko'p usullar bilan amalga oshirish mumkin; bir usul - barcha prefiks yig'indilarini hisoblash va ularni $1 - m$ 1-m indekslariga xaritalash, bu yerda $m$ - noyob prefiks yig'indilari soni. Keyin biz segment daraxti yoki Fenwick daraxtidan foydalanib, ushbu muammoni hal qilishimiz mumkin. Bu vaqt murakkabligini $O (n lo g n)$ \mathcal{O}(n \log n) ga olib keladi, bu esa Python yordamida hal qilish uchun etarlicha tez.

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