题解 | 离线询问+双指针做法

跟【小红的区间查询】这一题如出一辙，仍然可以离线查询，对查询进行排序后使用双指针优化。

构建前缀和数组 $S$ ，原问题等价问，第k个时刻处于前几个区间，大众做法是每次二分前缀和数组，找出第一个大于等于的S[k]，k问答案。

我们可以将每次询问保存起来，最后排序，排完序后是单调不减的，那么越往后的询问，对k的要求只会越来越大，因此我们枚举前缀和的时候不需要重新回退i=1开始，而是像双指针那样每次决策，这样下来，时间复杂度是 $O(n\log n+q)$ ，二分的做法是

$O(n+q\log n)$

最后跑出来是17ms，排名第7.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1e5+7;
typedef long long ll;
ll s[N];
int n,q;
vector<pair<int,int>> qu;
int ans[N];
void solve(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>s[i];
        s[i]+=s[i-1];
    }
    for(int i=1;i<=q;i++){
        int x;
        cin>>x;
        qu.push_back({x+1,i});
    }
    sort(qu.begin(),qu.end());
    int i=1;
    for(int j=0;j<qu.size();){
        int x=qu[j].first;
        int y=qu[j].second;
        while(i<=n &&s[i]<x){ //如果当前询问的时间已经大于了该分段
            i++;
        }
        ans[y]=i;
        j++;
    }
    for(int i=1;i<=q;i++){
        cout<<ans[i]<<"\n";
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int T=1;
    //cin>>T;
    while(T--)solve();
    return 0;
}