二分、前缀和

问题在于注意不到诸如寻找前缀和序列第一个不小于 $x$ 的元素下标的方法错误，本题实现过程中错误的实现方式使用 set 导致查找到的是最小的大于等于 $x$ 的元素的下标。已经通过排序后维护后缀信息的方式解决。

理解题意，给定一个由长度为 $n$ 的序列 $a$ 拼接得到的无限序列，多次询问这个序列的前缀和序列中第一个不小于 $x$ 的元素下标减去 $1$ 得到的值，若不存在则输出 $-1$。

如果 $\sum\limits_{i=1}^{n} a_i$ 不大于 $0$ 则询问答案必定不大于 $n-1$，对元素排序后维护后缀最小值。

若 $\sum\limits_{i=1}^{n} a_i$ 大于 $0$ 则询问答案必定不为 $-1$，首先找到序列 $a$ 的前缀和的最大值首次出现的位置 $pos$，称前缀和序列中所有下标满足 $p=pos+nk(k \in \mathbb{Z})$ 的元素为波峰。二分得到第一个不小于 $x$ 的波峰，答案必定不大于波峰编号且大于上一个波峰编号。然后在该波峰所属的长度为 $n$，对应序列 $a$ 的子序列中找到第一个不小于 $x$ 的数的位置。

代码实现中两部分可以合并，对于 $\sum\limits_{i=1}^{n} a_i$ 大于 $0$ 的情况二分出波峰所属对应 $a$ 的子序列的上一个子序列对 $x$ 的贡献（上一个子序列最后一个元素的值），把 $x$ 减掉这个贡献后的处理方式和 $\sum\limits_{i=1}^{n} a_i$ 不大于 $0$ 时相同，记得计入上一个子序列最后一个元素的下标对答案的贡献。注意二分时控制边界防止爆 long long。

由于 $n,m$ 同阶，时间复杂度 $O(n \log V)$。

#include<bits/stdc++.h>
using namespace std;
constexpr long long inf=5'000'000'000ll;
pair<long long,int> suf[200'005];
long long sum[200'005];
int n,m,pos,p[200'005];
void solution(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>sum[i],sum[i]+=sum[i-1];
    for(int i=1;i<=n;i++) suf[i]=make_pair(sum[i],i);
    sort(suf+1,suf+n+1);
    p[n]=suf[n].second;
    for(int i=n-1;i>=1;i--) p[i]=min(suf[i].second,p[i+1]);
    pos=n+1,sum[n+1]=LONG_LONG_MIN;
    for(int i=1;i<=n;i++) if(sum[i]>sum[pos]) pos=i;
    for(int i=1;i<=m;i++){
        static long long x,add,ans;
        cin>>x,add=0ll;
        if(sum[n]>0ll){
            long long l=1ll,r=(inf+sum[n]-1)/sum[n],aim=0ll;
            while(l<=r){
                long long mid=(l+r)>>1;
                if(sum[pos]+sum[n]*(mid-1)<x) l=mid+1;
                else aim=mid,r=mid-1;
            }
            add=(aim-1)*n,x-=(aim-1)*sum[n];
        }
        int it=lower_bound(suf+1,suf+n+1,make_pair(x,0))-suf;
        if(it==n+1) ans=-1ll;
        else ans=p[it]+add-1;
        cout<<ans<<" \n"[i==m];
    }
}
int T;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>T;
    while(T--) solution();
    return 0;
}