
ZOJ Problem Set  3943
The Himalayas or Himalaya is a mountain range in the Indian subcontinent, which separates the IndoGangetic Plain from the Tibetan Plateau. This range is home to nine of the ten highest peaks on Earth, including the highest above sea level, Mount Everest. The Himalayas have profoundly shaped the cultures of South Asia. Many Himalayan peaks are sacred in both Buddhism and Hinduism. By Sudan Shrestha. License: CCbysa 3.0 Edward, the headmaster of Marjar University, is doing a research about the Himalayas. To simplify the model, Edward thinks that there are N mountains in the Himalayas and they are lined up. Edward numbered them from 1 to N from left to right. What's more, Edward defines peaks of the Himalayas which satisfy:
Then the ith mountain is called a peak. Furthermore, Edward found an interesting fact about the Himalayas from its history: earthquakes will change the height of some continuous mountains. To be more specific, for an earthquake, we record it as (L, R, A, B), which means the height of the ith (L ≤ i ≤ R) mountain will change by A + (i  L) * B after the earthquake. Edward wants to know the amount of peaks after each earthquake. Please tell him. InputThere are multiple test cases. The first line of input contains an integer T (≤ 10) indicating the number of test case. For each test case: The first line contains two integers N, M (1 ≤ N, M ≤ 10^{5}) indicating the number of the mountains and the number of the earthquakes. The next line contains N (1 ≤ N ≤ 10^{5}) integers, the ith integer is the initial height H_{i} of the ith mountain (0 ≤ H_{i} ≤ 10^{5}). Then followed by M lines, each line contains four integers L, R, A, B (1 ≤ L ≤ R ≤ N, 1 ≤ B ≤ 10^{5}, 10^{5} ≤ A ≤ 10^{5}) of an earthquake, in chronological order. OutputFor each earthquake, output the amount of peak after it. Sample Input2 4 2 1 5 3 0 3 4 1 1 3 4 2 1 4 2 1 5 3 0 3 4 1 1 3 4 1 1 Sample Output1 1 1 0 Hint1 5 3 0 > 1 5 4 2 > 1 5 6 5 Author: CHEN, Weijie Source: The 13th Zhejiang Provincial Collegiate Programming Contest 