https://www.luogu.com.cn/problem/CF1923C

Find B

题面翻译

定义一个长为 $m$ 的正整数序列 $a$ 是好的，当且仅当存在长为 $m$ 的正整数序列 $b$ 满足以下条件：

• $\displaystyle\sum_{i=1}^m a_i=\sum_{i=1}^m b_i;$
• $\forall i\in[1,m],a_i\ne b_i.$

给定一个长为 $n$ 的正整数序列 $c$ 和 $q$ 个询问，每次询问给出 $l_i,r_i$，要求判断 $c_{l_i},c_{l_i+1},\dots,c_{r_i-1},c_{r_i}$ 是否是好的序列。每个测试点 $t$ 组测试用例。

Translated by Luzhuoyuan.

题目描述

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.

输入格式

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 $ .

输出格式

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.

样例 #1

样例输入 #1

1
5 4
1 2 1 4 5
1 5
4 4
3 4
1 3

样例输出 #1

YES
NO
YES
NO

因为没有规定必须用原来的数字，所以可以把总和统计起来，暂时把所有的元素都设为一，如果原数组有一的，就用剩下的总和分给1，如果不够让所有的1都加到2以上，就NO

const int N = 300010;
ll a[N];
ll b[N];
ll c[N];
void solve()
{
    int n, q;
    cin >> n >> q;

    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        b[i] = a[i] + b[i - 1];
        if (a[i] == 1)
        {
            c[i] = c[i - 1] + 1;
        }
        else c[i] = c[i - 1];
    }
    while (q--)
    {
        int l, r;
        cin >> l >> r;
        if (l == r)
        {
            cout << "NO" << '\n';
            continue;
        }
        ll yi = c[r] - c[l - 1];
        ll ans = b[r] - b[l - 1];
        if (ans - (r - l + 1) < yi) cout << "NO" << '\n';
        else cout << "YES" << '\n';
    }
}