I.自学（逃课）
该题并不根据实际情况改编，请大家认真上课。
题目要意:一个长为的数组，每次查询输入一对,求最大的使得成立，如果,则
解法 前缀和+二分
该题中，求一个最大的使得某个式子成立，我们很容易想到可以二分答案，显然的，当时，若能符合要求，也一定能符合要求，那么的取值有单调性，所以可以进行二分
那么二分需要我们快速求出的和，容易想到前缀和进行优化，复杂度为,可以通过本题
事实上，这是一道较为经典的二分和前缀和结合的题目。
大家可以想一想，如果题目要求在每次查询前，对某个进行修改，应该怎么做呢？答案在代码后面揭晓
特别的是，本题的数据范围会超过能表示的范围，请使用
以下为出题人代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
auto b = a;
for (int i = 2; i <= n; i++) {
a[i] += a[i - 1];
}
while (q--) {
int k, m;
cin >> k >> m;
if (b[k] > m) {
cout << 0 << endl;
continue;
}
auto xx = upper_bound(next(a.begin(), k), a.end(), m + a[k - 1]);
if (xx == a.end()) {
cout << n - k + 1 << endl;
continue;
}
if (*xx > m + a[k - 1])
xx--;
cout << xx - next(a.begin(), k) + 1 << endl;
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int __ = 1;
while (__--) {
solve();
}
return 0;
}
关于先前的问题，如果需要修改，我们显然需要使用一些更强的数据结构来进行区间查询，很容易想到线段树可以胜任，所以答案就是在线段树上二分，时间复杂度依然为