感染(high)

Description

与2D不同，现在给你n天的COVID-19新增感染人数和治愈人数，有q次询问，每次询问针对k，问至少多少天现在患病人数会大于等于k。

Input

第一行输入两个整数n(1 n 1e6)，q(1 q 1e6)。

第二行有n个正整数a_i​表示第i天新感染的人数(1 a_i 1e6)

第三行有n个正整数b_i​表示第i天新治愈的人数(1 b_i 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", (a_i - b_i) 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.