Skor#11806
Problem Yazarı: | Hasan Saleh (MathModel) |
Hazırlayan: | Hasan Saleh (MathModel) |
Editör: | Hasan Saleh (MathModel) |
Basit bir çözüm, dizideki tüm alt segmentleri döngü ile geçip puanları toplamaktır; bu \mathcal{O}(n^2) çözümü verir. Ancak bu çok yavaştır; bunu daha hızlı yapmalıyız.
Hesaplamayı hızlandırmak için, indeksinde biten her alt segment için, kaç tanesinin harika, kaç tanesinin mükemmel ve kaç tanesinin normal olduğunu hesaplamamız gerekiyor.
dizinin toplamı olsun. Alt segmentin toplamının \frac{s}{2}'den büyük olup olmadığını kolayca belirleyebiliriz; eğer büyükse harika olur; eğer küçükse normal olur ve çift ise ve alt segmentin toplamı \frac{s}{2}'ye eşitse mükemmel olur.
Böylece, her indeks için ön toplamı p_i almalı ve p_i - \frac{s}{2}'den büyük, eşit veya küçük olan segmentlerin sayısını saymalıyız. Bu birçok şekilde yapılabilir; bir yol, tüm ön toplamları hesaplayıp bunları 1-m indekslerine eşlemektir; burada farklı ön toplamların sayısıdır. Sonra bu problemi çözmek için bir segment ağacı veya Fenwick ağacı ile ikili arama kullanabiliriz. Bu, zaman karmaşıklığını \mathcal{O}(n \log n) yapar ki bu Python kullanarak çözmek için yeterince hızlıdır.
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()