Score#11806

Score (Editorial)

Problem Author:	Hasan Saleh (MathModel)
Prepared by:	Hasan Saleh (MathModel)
Editorial:	Hasan Saleh (MathModel)

A simple solution is to iterate through all subsegments in the array and sum the scores, which gives an $O (n^{2})$ \mathcal{O}(n^2) solution. However, this is too slow; we need to do it faster.

To speed up the computation, we need to calculate for each subsegment that ends at index $i$ , how many of them are wonderful, how many are perfect, and how many are normal.

Let $s$ be the sum of the array. We can easily determine if the sum of the subsegment is greater than $\frac{s}{2}$ \frac{s}{2}; it will be wonderful; if it is less than $\frac{s}{2}$ \frac{s}{2}, it will be normal, and if $s$ is even and the sum of the subsegment equals $\frac{s}{2}$ \frac{s}{2}, it will be perfect.

Thus, we need to get the prefix sum for each index $p_{i}$ p_i, and count the number of segments that are greater than, equal to, or less than $p_{i} - \frac{s}{2}$ p_i - \frac{s}{2}. This can be done in many ways; one way is to compute all prefix sums and map them to indices from $1 - m$ 1-m, where $m$ is the number of distinct prefix sums. Then we can use a segment tree or a Fenwick tree along with binary search to solve this problem. This will make the time complexity $O (n lo g n)$ \mathcal{O}(n \log n), which is fast enough to solve this using 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