Description
与2D不同，现在给你n天的COVID-19新增感染人数和治愈人数，有q次询问，每次询问针对k，问至少多少天现在患病人数会大于等于k。
Input
第一行输入两个整数n(1 n
1e6)，q(1
q
1e6)。
第二行有n个正整数ai表示第i天新感染的人数(1 ai
1e6)
第三行有n个正整数bi表示第i天新治愈的人数(1 bi
1e6)。
接下来q行，每行给出一个k(1 k
max_
)。
Output
对于每个询问，输出一个整数m，代表至少m天现在患病人数会大于等于k。
Sample Input 1
3 2
1 2 3
1 1 1
1
2</pre>
Sample Output 1
2
3
Source
nuoyanli.com
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6 + 5;
LL n, q, m;
LL sum[maxn];
LL a[maxn];
LL b[maxn];
LL que[maxn];
LL id[maxn];
int main()
{
scanf("%lld%lld",&n,&q);
memset(sum, 0, sizeof(sum));
for(int i = 1; i <= n; i++)
scanf("%lld",&a[i]);
for(int i = 1; i <= n; i++)
scanf("%lld",&b[i]);
for(int i = 1; i <= n; i++)
sum[i] = sum[i-1] + a[i] - b[i];
int cnt = 0;
que[cnt] = 0;
id[cnt] = 0;
for(int i = 1 ; i <= n; i++)
{
if(sum[i] > que[cnt])
{
que[++cnt] = sum[i];
id[cnt] = i;
}
}
while(q--)
{
scanf("%lld",&m);
printf("%lld\n",id[lower_bound(que, que + cnt, m) - que]);
}
return 0;
}
Analysis:
This Prefix Sum not monotonic, unlike the "mid", (ai - bi) may be negetive, so maintain a strictly monotonically increasing sequence.
detail:
1.Use another array 'que[]' to store the monotoniclly increasing sequence.
2.lower_bound().Dichotomy.
