https://codeforces.com/contest/1923/problem/C

题意

如果存在一个长度为 $m$ 的整数数组 $b$ 且以下条件成立，那么长度为 $m$ 的数组 $a$ 就被认为是好数组：

1. $\sum\limits_{i=1}^{m} a_i = \sum\limits_{i=1}^{m} b_i$;
2. $a_i \neq b_i$；
3. $b_i > 0$。

给你一个长度为 $n$ 的数组 $a$。数组中的每个元素都大于 $0$。

你必须回答 $q$ 个查询。在第 $i$ 个查询中，你必须确定子数组 $a_{l_{i}}, a_{l_{i}+1}, \dots, a_{r_{i}}$ 是否是好数组。

题解

判断一个数组 $a$ 好不好，我们可以转化为能否构造出合法的 $b$。

首先，如果 $[l, r]$ 中所有元素 $a_i$ 均大于 $1$, 那么子数组 $a_l, a_{l+1}, \dots, a_r$，必然是好数组，因为我们可以将 $a_{l \dots r - 1}$ 分出 $r - l$ 加在 $a_r$ 上，得到满足条件的 $b$ 数组。

于是我们观察到，影响一个数组 $a$“不好”的原因就是 $a$ 中存在 $1$。因为 $a_i = 1$ 时无法减少自己的值，需要其他元素减少值补给自己，而当其他元素可以补给自己的值不够时，则无法构造出满足条件的 $b$ 数组。

于是我们预处理每个前缀最多有多少值可以补给区间中 $a_i = 1$ 的元素，$f_i = \sum\limits_{j = 1}^{i}{(a_j - 1)}$。和每个前缀有多少值为 $1$ 的元素。
最后对每个询问进行检查即可。

#include <iostream>
using namespace std;
typedef long long ll;
const int maxn = 300010;
int t, n, m, a[maxn];
ll s[maxn], p[maxn];
int main () {
  ios::sync_with_stdio (false);
  cin.tie (0);
  cin >> t;
  while (t--) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
      cin >> a[i];
      s[i] = s[i - 1] + (a[i] == 1);
      p[i] = p[i - 1] + (a[i] - 1);
    }
    for (int i = 1; i <= m; i++) {
      int l, r; cin >> l >> r;  
      if (l == r) cout << "NO\n";
      else cout << ((s[r] - s[l - 1] <= p[r] - p[l - 1]) ? "YES" : "NO") << '\n';
    }
  }
  return 0;
}