题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 3 \times 10^5$，$q$之和$\leq 3 \times 10^5$。

每组数据输入$n(1 \leq n \leq 3 \times 10^5)$、$q(1 \leq q \leq 3 \times 10^5)$和长为$n$的数组$a(1 \leq a[i] \leq 10^9)$，下标从$1$开始。

然后输入$q$个询问，每个询问输入两个数$L$和$R$，表示下标从$L$到$R$的连续子数组$b(1 \leq L \leq R \leq n)$。

对于每个询问，你需要构造一个和$b$一样长的数组$c$，要求：

1. $sum(c)=sum(b)$。
2. 所有$c[i]$都不等于$b[i]$。
3. 所有$c[i]$都是正数。

能否构造？输出YES或NO。

输入样例

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

输出样例

YES
NO
YES
NO

算法

贪心构造

将$a$数组中元素值等于$1$的索引存入数组$one$中，分为以下几种情况：

1. 如果$L=R$肯定就没有办法了，输出NO。
2. 如果$[L,R]$中没有$1$，那就让$R-L$个数减去$1$，剩下的那个数加上$R-L$，输出YES。
3. 否则在$one$上二分求出有多少个$1$落在了子数组$[L,R]$中。这$cnt_1$个$1$都增加$1$，那么$\gt 1$的数就需要减去总和$cnt_1$。而为了让剩下的那些数的总和$sum\_other$在减去$cnt_1$后每个数还是正数，就要求$sum\_other-cnt_1 \geq R-L+1-cnt_1$，只要满足这个答案就是YES，否则是NO。

复杂度分析

时间复杂度

预处理出$one$以及$a$的前缀和数组$s$（为了快速计算$sum\_other$）只需要遍历一遍数组，时间复杂度为$O(n)$。而处理每个询问的时候在最差情况下需要对$one$数组进行两次二分，因此时间复杂度为$O(qlog_2n)$。整个算法的时间复杂度为$O(n+qlog_2n)$。

空间复杂度

空间消耗就是$one$数组和前缀和$s$数组，两个数组都是$O(n)$的，这也是整个算法的额外空间复杂度。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 300010;
int T, n, q, a[N];
LL s[N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &q);
        vector<int> one;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            s[i] = s[i - 1] + a[i];
            if(a[i] == 1) one.push_back(i);
        }
        for(int i = 1; i <= q; i++) {
            int l, r;
            scanf("%d%d", &l, &r);
            if(l == r) {
                puts("NO");
            }else {
                int cnt1 = one.empty()? 0: upper_bound(one.begin(), one.end(), r) - lower_bound(one.begin(), one.end(), l);
                if(cnt1 == 0) {
                    puts("YES");
                }else {
                    if(cnt1 == r - l + 1) {
                        puts("NO");    // 区间中全是1
                    }else {
                        int cnt_other = r - l + 1 - cnt1;
                        LL sum_other = s[r] - s[l - 1] - cnt1;
                        puts(sum_other - cnt1 >= cnt_other? "YES": "NO");
                    }
                }
            }
        }
    }
    return 0;
}