Codeforces Round #827 (Div. 4) E. Scuza

• $前缀和$ + $二分$
• Let’s compute the prefix sums of the array $a$: let $b_i$= $a_1+\cdots +a_i$. Rephrasing the problem: for each question containing an integer $k$, we need to find the largest ai such that $a_1,\dots ,a_i$ are all at most $k$, and then output $b_i$. In other words, $max(a_1,\dots ,a_i)\le k$.
• Let’s make the prefix maximums of the array: $let{m}_i=max(a_1,\dots ,a_i)$. Then we need to find the largest $i$ such that $m_i\le k$, which is doable using binary search, since the array m is non-decreasing. Once we find the index $i$, we simply need to output $b_i$.
• The time complexity is $O(nlogn)$ per testcase.
• 所有数字都比当前数字大就意味着不能上任意一阶台阶，所以输出0。

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;

int main()
{
    int T;cin>>T;
    while (T--)
    {
        int n,q;cin>>n>>q;
        vector<LL> a(n),s(n);
        vector<LL> k(q+1);
        for(int i=0;i<n;i++) cin>>a[i],s[i]=a[i];
        for(int i=0;i<q;i++) cin>>k[i];

        for(int i=1;i<n;i++) a[i]=max(a[i],a[i-1]);
        for(int i=1;i<n;i++) s[i]+=s[i-1];

        for(int i=0;i<q;i++)
        {
            int x=upper_bound(a.begin(),a.end(),k[i])-a.begin();
            if(x==0) cout<<"0 ";
            else cout<<s[x-1]<<" ";
        }
        cout<<endl;
    }
    return 0;
}