[USACO 2009 Dec S]Music Notes

subject ： [USACO 2009 Dec S]Music Notes , ha-ha , Let's look at a question with dichotomy today , This is from USACO A question on , Okay , Let's have a look at the meaning of the title ：

The title description is copied , There may be some display errors , I'll put the title link below ！
Topic link ： [USACO 2009 Dec S]Music Notes

Title Description

FJ is going to teach his cows how to play a song. The song consists of N (1 <= N <= 50,000) notes, and the i-th note lasts for Bi (1 <= Bi <= 10,000) beats (thus no song is longer than 500,000,000 beats). The cows will begin playing the song at time 0; thus, they will play note 1 from time 0 through just before time B1, note 2 from time B1 through just before time B1 + B2, etc. However, recently the cows have lost interest in the song, as they feel that it is too long and boring. Thus, to make sure his cows are paying attention, he asks them Q (1 <= Q <= 50,000) questions of the form, "In the interval from time T through just before time T+1, which note should you be playing?" The cows need your help to answer these questions which are supplied as Ti (0 <= Ti <= end_of_song).

Input description

• Line 1: Two space-separated integers: N and Q
• Lines 2…N+1: Line i+1 contains the single integer: Bi
• Lines N+2…N+Q+1: Line N+i+1 contains a single integer: Ti

Output description

• Lines 1…Q: Line i of the output contains the result of query i as a single integer.

Example 1

Input

3 5
2
1
3
2
3
4
0
1

Output

2
3
3
1
1

Ideas :

Adopt the idea of prefix and dichotomy , It will be solved soon

Let's look at success AC The code of ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,q;
int a[1000010];
int sum[1000010];// Storing prefixes and 
int main(){
    
    ios::sync_with_stdio(false);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
    
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    while(q--){
    
        int x;  cin>>x;
        int ans=upper_bound(sum+1,sum+n+1,x)-sum;// Minus the starting position here is the subscript of the element 
        cout<<ans<<"\n";
    }
    return 0;
}

Thanks for reading , Because the author level is limited , There are inevitably shortcomings , If the reader finds a problem , Please criticize , Leave a message in the message area or send a private message to inform , I will revise it as soon as possible . If you guys have any good solutions , Or meaningful solutions can be displayed in the comment area , Thank you very much .
Writing is not easy to , I hope all bosses will praise me , Add a focus on !