Game with Stones (Codeforces 1588C)
Tags: Greedy, divide and conquer

Bob decided to take a break from calculus homework and designed a game for himself. The game is played on a sequence of piles of stones, which can be described with a sequence of integers $$$s_1, \ldots, s_k$$$, where $$$s_i$$$ is the number of stones in the $$$i$$$-th pile. On each turn, Bob picks a pair of non-empty adjacent piles $$$i$$$ and $$$i+1$$$ and takes one stone from each. If a pile becomes empty, its adjacent piles do not become adjacent. The game ends when Bob can't make turns anymore. Bob considers himself a winner if at the end all piles are empty.We consider a sequence of piles winning if Bob can start with it and win with some sequence of moves.You are given a sequence $$$a_1, \ldots, a_n$$$, count the number of subsegments of $$$a$$$ that describe a winning sequence of piles. In other words find the number of segments $$$[l, r]$$$ ($$$1 \leq l \leq r \leq n$$$), such that the sequence $$$a_l, a_{l+1}, \ldots, a_r$$$ is winning.

Input: Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 3 \cdot 10^5$$$) — the number of test cases. Description of the test cases follows.The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$).The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$).It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output: Print a single integer for each test case — the answer to the problem.

Note: In the first test case, Bob can't win on subsegments of length $$$1$$$, as there is no pair of adjacent piles in an array of length $$$1$$$.In the second test case, every subsegment is not winning.In the fourth test case, the subsegment $$$[1, 4]$$$ is winning, because Bob can make moves with pairs of adjacent piles: $$$(2, 3)$$$, $$$(1, 2)$$$, $$$(3, 4)$$$. Another winning subsegment is $$$[2, 3]$$$.

Sample Inputs:
6
2
2 2
3
1 2 3
4
1 1 1 1
4
1 2 2 1
4
1 2 1 2
8
1 2 1 2 1 2 1 2

Sample Outputs:
1
0
4
2
1
3

Solution (Python):
import sys
import math
inpu = sys.stdin.readline
prin = sys.stdout.write

def find(a, l, r):
    if r - l == 1:
        if a[l] == 0:
            return 1
        else:
            return 0
    if r - l == 2:
        tot = 0
        if a[l] == 0:
            tot += 1
        if a[l + 1] == 0:
            tot += 1
        if a[l] == a[l + 1]:
            tot += 1
        return tot
    mid = (l + r) // 2
    left = find(a, l, mid)
    right = find(a, mid, r)
    altleft = {}
    altright = {}
    rsum = 0
    diff = 0
    smleven = float('inf')
    bigodd = -smleven
    for i in range(mid, r):
        if diff % 2 == 0:
            if rsum < smleven:
                smleven = rsum
        elif rsum > bigodd:
            bigodd = rsum
        diff += 1
        if diff % 2 == 0:
            rsum += a[i]
        else:
            rsum -= a[i]
        if diff % 2 == 0 and rsum <= smleven and (rsum >= bigodd):
            if rsum in altright:
                altright[rsum] += 1
            else:
                altright[rsum] = 1
        elif diff % 2 == 1 and rsum <= smleven and (rsum >= bigodd) and (a[i] <= a[i - 1]):
            if rsum in altright:
                altright[rsum] += 1
            else:
                altright[rsum] = 1
    lsum = 0
    diff = 0
    bigeven = -float('inf')
    smlodd = -bigeven
    for i in range(mid - 1, l - 1, -1):
        if diff % 2 == 0:
            if lsum > bigeven:
                bigeven = lsum
        elif lsum < smlodd:
            smlodd = lsum
        diff += 1
        if diff % 2 == 1:
            lsum += a[i]
        else:
            lsum -= a[i]
        if diff % 2 == 0 and lsum <= smlodd and (lsum >= bigeven):
            if lsum in altleft:
                altleft[lsum] += 1
            else:
                altleft[lsum] = 1
        elif diff % 2 == 1 and lsum <= smlodd and (lsum >= bigeven) and (a[i] <= a[i + 1]):
            if lsum in altleft:
                altleft[lsum] += 1
            else:
                altleft[lsum] = 1
    tot = 0
    for guy in altleft:
        if -guy in altright:
            tot += altleft[guy] * altright[-guy]
    return tot + left + right
t = int(inpu())
for _ in range(t):
    n = int(inpu())
    a = list(map(int, inpu().split()))
    prin(str(find(a, 0, n)))
    prin('\n')

Solution (Python):
import random
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def sparse_table(a, b):
    (mi, ma) = ([], [])
    (s0, s1, l) = (list(a), list(b), 1)
    mi.append(s0)
    ma.append(s1)
    while 2 * l <= len(a):
        s2 = [min(s0[i], s0[i + l]) for i in range(len(s0) - l)]
        s3 = [max(s1[i], s1[i + l]) for i in range(len(s1) - l)]
        mi.append(list(s2))
        ma.append(list(s3))
        (s0, s1) = (s2, s3)
        l *= 2
    return (mi, ma)

def get_min(l, r, mi):
    if l > r:
        return inf
    d = (r - l + 1).bit_length() - 1
    ans = min(mi[d][l], mi[d][r - pow2[d] + 1])
    return ans

def get_max(l, r, ma):
    if l > r:
        return -inf
    d = (r - l + 1).bit_length() - 1
    ans = max(ma[d][l], ma[d][r - pow2[d] + 1])
    return ans
t = int(input())
ans = []
r = random.randint(1, pow(2, 50) - 1)
inf = pow(10, 15) + 1
pow2 = [1]
for _ in range(20):
    pow2.append(2 * pow2[-1])
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    u = [0] * (n + 1)
    for i in range(n):
        u[i + 1] = u[i] + a[i] if not i % 2 else u[i] - a[i]
    nx = [-1] * (n + 1)
    d = dict()
    for i in range(n, -1, -1):
        if u[i] ^ r in d:
            nx[i] = d[u[i] ^ r]
        d[u[i] ^ r] = i
    (x, y) = ([inf] * (n + 1), [-inf] * (n + 1))
    for i in range(n + 1):
        if i % 2:
            x[i] = u[i]
        else:
            y[i] = u[i]
    (mi, ma) = sparse_table(x, y)
    dp = [0] * (n + 1)
    for l in range(n):
        if nx[l] == -1:
            continue
        r = nx[l]
        if get_max(l + 1, r - 1, ma) < u[l] < get_min(l + 1, r - 1, mi):
            dp[r] = dp[l] + 1
    ans0 = sum(dp)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))

Solution (Python):
import random
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def sparse_table(a, b):
    (mi, ma) = ([], [])
    (s0, s1, l) = (list(a), list(b), 1)
    mi.append(s0)
    ma.append(s1)
    while 2 * l <= len(a):
        s2 = [min(s0[i], s0[i + l]) for i in range(len(s0) - l)]
        s3 = [max(s1[i], s1[i + l]) for i in range(len(s1) - l)]
        mi.append(list(s2))
        ma.append(list(s3))
        (s0, s1) = (s2, s3)
        l *= 2
    return (mi, ma)

def get_min(l, r, mi):
    if l > r:
        return inf
    d = (r - l + 1).bit_length() - 1
    ans = min(mi[d][l], mi[d][r - pow2[d] + 1])
    return ans

def get_max(l, r, ma):
    if l > r:
        return -inf
    d = (r - l + 1).bit_length() - 1
    ans = max(ma[d][l], ma[d][r - pow2[d] + 1])
    return ans
t = int(input())
ans = []
r = random.randint(1, pow(2, 50) - 1)
inf = pow(10, 15) + 1
pow2 = [1]
for _ in range(20):
    pow2.append(2 * pow2[-1])
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    u = [0] * (n + 1)
    for i in range(n):
        u[i + 1] = u[i] + a[i] if not i % 2 else u[i] - a[i]
    nx = [-1] * (n + 1)
    d = dict()
    for i in range(n, -1, -1):
        if u[i] ^ r in d:
            nx[i] = d[u[i] ^ r]
        d[u[i] ^ r] = i
    (x, y) = ([inf] * (n + 1), [-inf] * (n + 1))
    for i in range(n + 1):
        if i % 2:
            x[i] = u[i]
        else:
            y[i] = u[i]
    (mi, ma) = sparse_table(x, y)
    dp = [0] * (n + 1)
    for l in range(n):
        if nx[l] == -1:
            continue
        r = nx[l]
        if get_max(l + 1, r - 1, ma) < u[l] < get_min(l + 1, r - 1, mi):
            dp[r] = dp[l] + 1
    ans0 = sum(dp)
    ans.append(ans0)
sys.stdout.write('\n'.join(map(str, ans)))