题目描述
难度分:1400
输入T(≤104)表示T组数据。所有数据的n之和≤3×105，q之和≤3×105。
每组数据输入n(1≤n≤3×105)、q(1≤q≤3×105)和长为n的数组a(1≤a[i]≤109)，下标从1开始。
然后输入q个询问，每个询问输入两个数L和R，表示下标从L到R的连续子数组b(1≤L≤R≤n)。
对于每个询问，你需要构造一个和b一样长的数组c，要求：
- sum(c)=sum(b)。
- 所有c[i]都不等于b[i]。
- 所有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中，分为以下几种情况：
- 如果L=R肯定就没有办法了，输出
NO。 - 如果[L,R]中没有1，那就让R−L个数减去1，剩下的那个数加上R−L，输出
YES。 - 否则在one上二分求出有多少个1落在了子数组[L,R]中。这cnt1个1都增加1，那么>1的数就需要减去总和cnt1。而为了让剩下的那些数的总和sum_other在减去cnt1后每个数还是正数，就要求sum_other−cnt1≥R−L+1−cnt1，只要满足这个答案就是
YES，否则是NO。
复杂度分析
时间复杂度
预处理出one以及a的前缀和数组s（为了快速计算sum_other）只需要遍历一遍数组，时间复杂度为O(n)。而处理每个询问的时候在最差情况下需要对one数组进行两次二分，因此时间复杂度为O(qlog2n)。整个算法的时间复杂度为O(n+qlog2n)。
空间复杂度
空间消耗就是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;
}
