#include <iostream>
using namespace std;
const int N = 100001;
int n, a[N];
int check(int a, int b, int c) {
return (a <= c && c <= b) || (b <= c && c <= a);
}
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i += 1) {
cin >> a[i];
a[i] += a[i - 1];
}
int q;
cin >> q;
while(q--) {
int L, R;
cin >> L >> R;
int target = (a[L] + a[R]) / 2;
int pos = -1;
while(L != R) {
int mid = (L + R) / 2;
if(a[mid] == target) {
pos = mid;
break;
}
if(check(a[L], a[mid - 1], target))
R = mid - 1;
else
L = mid + 1;
}
if(pos == -1)
cout << "NO" << endl;
else
cout << "YES" << endl;
}
}
判断题
1) 该算法的时间复杂度为Θ((n+q)*log(n))。（ ）
2) 程序输出NO时，代表不存在l<=x<=r，使得a[x]=target。（ ）。
选择题
3) 当输入的n = 3，输入的a[i]分别为2,3,1, q=2, 两组询问分别为L=2,R=3和L=1,R=3时，输出的是（ ）。
4) 当输入的n = 100，输入的a[i]当i为奇数时为-1，偶数时为1, q=2, 两组询问分别为L=1,R=100和L=30,R=40时，输出的是（ ）。
5) 当a满足以下哪种条件时，程序总是输出YES（ ）。