To solve this problem, we need to count the number of subarrays where the number of elements in array A that are greater than the corresponding elements in array B is more than those that are less.

Approach

1. Transform Arrays: Convert the problem into a sum problem by creating an array C where each element is:

   • 1 if A[i] > B[i]
   • -1 if A[i] < B[i]
   • 0 otherwise.

2. Prefix Sum: Use prefix sums to determine the sum of any subarray. The sum of a subarray from index i to j in C is prefix[j+1] - prefix[i]. We need this sum to be positive (since this means more elements in A are greater than B in the subarray).

3. Fenwick Tree: To efficiently count the number of valid subarrays, we use a Fenwick Tree (Binary Indexed Tree) to keep track of the frequency of prefix sums. For each prefix sum, we query how many previous prefix sums are smaller than the current prefix sum (this gives the number of valid subarrays ending at the current position).

Solution Code

class FenwickTree:
    def __init__(self, size):
        self.n = size
        self.tree = [0] * (self.n + 2)  # 1-based indexing

    def update(self, idx, delta):
        while idx <= self.n:
            self.tree[idx] += delta
            idx += idx & -idx

    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    n = int(input[ptr])
    ptr +=1
    A = list(map(int, input[ptr:ptr+n]))
    ptr +=n
    B = list(map(int, input[ptr:ptr+n]))
    ptr +=n

    C = []
    for a, b in zip(A, B):
        if a > b:
            C.append(1)
        elif a < b:
            C.append(-1)
        else:
            C.append(0)

    max_shift = 2 * n + 1  # Shifted values range from 1 to 2n+1
    ft = FenwickTree(max_shift)

    current_sum = 0
    total = 0
    # Add initial prefix sum (0)
    shifted_initial = 0 + n + 1
    ft.update(shifted_initial, 1)

    for num in C:
        current_sum += num
        shifted = current_sum + n + 1
        # Query number of prefix sums less than current_sum (shifted-1)
        count = ft.query(shifted - 1)
        total += count
        # Update Fenwick Tree with current shifted value
        ft.update(shifted, 1)

    print(total)

if __name__ == "__main__":
    main()

Explanation

1. Transformation: The array C helps us convert the problem into checking if the sum of a subarray is positive. This is because the sum of C over a subarray gives the difference between the count of elements where A[i] > B[i] and A[i] < B[i].

2. Prefix Sum: The prefix sum array allows us to compute the sum of any subarray in constant time. For a subarray from i to j, the sum is prefix[j+1] - prefix[i].

3. Fenwick Tree: This data structure efficiently handles two operations:

   • Update: Add the current prefix sum to the tree.
   • Query: Count the number of previous prefix sums that are smaller than the current prefix sum (this gives the number of valid subarrays ending at the current position).

This approach ensures that we handle the problem in O(n log n) time, which is efficient for large values of n (up to 100,000). The Fenwick Tree operations are logarithmic, making the solution scalable.

Complexity

• Time Complexity: O(n log n) (each element is processed once, and each Fenwick Tree operation is O(log n)).
• Space Complexity: O(n) (for the array C and the Fenwick Tree).

This solution efficiently counts the valid subarrays and handles all edge cases, including equal elements and large input sizes.

作者声明:本文包含人工智能生成内容。