Balanced subarrays

1

4 votes
Algorithms, Dynamic Programming, Tree, Trees, C++
Problem

A subarray is said to be balanced if the number of pairs (i, i+1), such that A[i] is even and A[i+1] is odd, is equal to the number of pairs (i, i+1) such that A[i] is odd and A[i+1] is even.

You are given an array A of N elements.

You are performing Q queries on it. In each query, you are given L R X in which you add X to all the elements in range L to R (inclusive). After each query, print the probability that if you randomly select a subarray in A, then that subarray is balanced.

It can be proved that the probability is of the form PQ where P and Q are both coprimes. Print PQ1 modulo 1000000007 (109+7) for each query.

Input format

  • The first line contains an integer N denoting the number of elements in the array.
  • The next line contains N space-separated integers.
  • The next line contains an integer Q denoting the number of queries.
  • The next Q lines contain three space-separated integers L R X.

Output format

Print a single integer denoting the probability for each query.

Constraints
1N, Q1e51A[i], X1e18
 

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

After Query 1 , array is 14 3 58 252 63. 
Balanced Subarrays are : [1], [2], [3], [4], [5] , [1,3], [1,4], [3,4] , [2,5] .

Probability = 9 / 15 

Output is modulo 10^9 + 7.

Editor Image

?