Music Notes

题目描述：

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).


Consider this song with three notes of durations 2, 1, and 3 beats:
Beat:   0    1    2    3    4    5    6    ...
        |----|----|----|----|----|----|--- ...
        1111111111     :              :
                  22222:              :
                       333333333333333:

Here is a set of five queries along with the resulting answer:
   Query    Note
     2        2
     3        3
     4        3
     0        1
     1        1

题意：

有n种音符，每种音符叫 i（ 1 <= i <= n )，b[i]表示 i 音符持续的时间，m次询问，问你t[i]时刻放的是什么音符

思路：

二分查找 + 前缀和

对b[i]做一次前缀和，然后对于每次询问，都去前缀和里面二分查找b[i]，输出对应的位置即可

二分可以用lowerbound，也可以手写，这里两种都给出来（实测lower bound比手写快

坑点：

二分查找的时候是去查找t[i] + 1, 找到的pos 最后输出的时候要+1

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}

ll k;
ll n, m, x;
ll pos;
vector<ll>sum;

int main(){
    io;
    cin>>n>>m;
    k = 0;
    for(int i = 1; i <= n; ++i){
        cin>>x;
        k += x;
        sum.push_back(k);
    }
    for(int i = 1; i <= m; ++i){
        cin>>x;
        pos = lower_bound(sum.begin(), sum.end(),x + 1) - sum.begin();
        cout<<pos + 1<<endl;
    }

    return 0;
}

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 50
#define endl '\n'
#define seed 13331
#define mod 1000000007
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef  long long ll ;
//不开longlong见祖宗！
//inline __int128 read(){__int128 x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-'){f = -1;}ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;}
//inline void print(__int128 x){if(x < 0){putchar('-');x = -x;}if(x > 9){print(x / 10);}putchar(x % 10 + '0');}
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}
inline void write(int x){if (x < 0) {x = ~x + 1; putchar('-');}if (x > 9){write(x / 10);}putchar(x % 10 + '0');}


int t, n, m, x;
int sum[MAX];

int lowerbound(int x){
    int l = 1, r = n;
    while (l <= r) {
        int mid = (l + r) / 2;
        if(x <= sum[mid])r = mid - 1;
        else l = mid + 1;
    }
    return l - 1;
}

int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; ++i){
        cin>>x;
        sum[i] = sum[i - 1] + x;
    }
    for(int i = 1; i <= m; ++i){
        cin>>x;
        cout<<lowerbound(x + 1) + 1<<endl;
    }

    return 0;
}