Find B
Contest: Educational Codeforces Round 162 (Rated for Div. 2)
Difficulty rating: 1400
Tags: constructive algorithms, greedy

An array $$$a$$$ of length $$$m$$$ is considered good if there exists an integer array $$$b$$$ of length $$$m$$$ such that the following conditions hold:

1. $$$\sum\limits_{i=1}^{m} a_i = \sum\limits_{i=1}^{m} b_i$$$;
2. $$$a_i \neq b_i$$$ for every index $$$i$$$ from $$$1$$$ to $$$m$$$;
3. $$$b_i > 0$$$ for every index $$$i$$$ from $$$1$$$ to $$$m$$$.

You are given an array $$$c$$$ of length $$$n$$$. Each element of this array is greater than $$$0$$$.

You have to answer $$$q$$$ queries. During the $$$i$$$-th query, you have to determine whether the subarray $$$c_{l_{i}}, c_{l_{i}+1}, \dots, c_{r_{i}}$$$ is good.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the length of the array $$$c$$$ and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^9$$$).

Then $$$q$$$ lines follow. The $$$i$$$-th of them contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the borders of the $$$i$$$-th subarray.

Additional constraints on the input: the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$; the sum of $$$q$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output format:
For each query, print YES if the subarray is good. Otherwise, print NO.

You can output each letter of the answer in any case (upper or lower). For example, the strings yEs, yes, Yes, and YES will all be recognized as positive responses.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
1
5 4
1 2 1 4 5
1 5
4 4
3 4
1 3

Example output:
YES
NO
YES
NO

Editorial:
At first, let's precalculate the array of prefix sum and the number of elements equal to one on prefix (let's denote them as $$$sum[]$$$ and $$$cnt1[]$$$). More formally, $$$sum_i = \sum_{k=1}^{i} c_i$$$ and $$$cnt1_i = \sum_{k=1}^{i} (is\_1(c_i))$$$, where the function $$$is\_1(x)$$$ returns $$$1$$$ if $$$x$$$ equals $$$1$$$ and $$$0$$$ otherwise . For example, if $$$c = [5, 1, 1, 2, 1, 10]$$$, then $$$sum = [0, 5, 6, 7, 9, 10, 20]$$$ and $$$cnt_1 = [0, 0, 1, 2, 2, 3, 3]$$$.
Now we can answer the query $$$l$$$, $$$r$$$. For this, let's calculate the sum on subarray $$$c_l, \dots, c_r$$$ and the number of elements equal to $$$1$$$ on subarray $$$c_l, \dots, c_r$$$ (let's denote it as $$$cur\_sum$$$ and $$$cur\_cnt1$$$). We can do it by precalculated arrays $$$sum$$$ and $$$cnt1$$$:
• $$$cur\_sum = sum_r - sum _{l - 1}$$$;
• $$$cur\_cnt1 = cnt1_r - cnt1 _{l - 1}$$$.
To answer query $$$l$$$, $$$r$$$ at first let's try to find the array $$$b$$$ with the minimum value of $$$\sum b_i$$$. For this, for indexes $$$i$$$, where $$$c_i = 1$$$ we have to set $$$b_i = 2$$$, and for indexes $$$i$$$, where $$$c_i > i$$$ we have to set $$$b_i = 1$$$. Thus, the sum of all elements in array $$$b$$$ equal to $$$cnt_1 \cdot 2 + (r - l + 1) - cnt_1$$$ or $$$(r - l + 1) + cnt_1$$$. Now we have three cases:
• If this sum is greater than $$$\sum_{i=l}^{r} c_i$$$ then the answer is $$$NO$$$;
• If this sum is equal to $$$\sum_{i=l}^{r} c_i$$$ then the answer is $$$YES$$$;
• If this sum is greater than $$$\sum_{i=l}^{r} c_i$$$ then we can add this excess to the maximal element in array $$$b$$$. In this case, the answer is $$$YES$$$.