比赛 期末考试1 评测结果 AAAAAAAAAA
题目名称 Interactive 最终得分 100
用户昵称 Ruyi 运行时间 2.841 s
代码语言 C++ 内存使用 16.55 MiB
提交时间 2026-02-08 10:33:23
显示代码纯文本
#include<bits/stdc++.h>
#define llg long long
#define N 200001
using namespace std;
llg n,q,k,a[N],s[N],bcnt[N],totb[N],x;
struct tree{llg num,l,r;}t[4*N];
void build(int l,int r,int p){
    t[p].l=l;
	t[p].r=r;
    if(l==r){
        t[p].num=s[l];
        return;
    }
    llg mid=(l+r)/2;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    t[p].num=min(t[p*2].num,t[p*2+1].num);
    return ;
}
llg query(int sL,int sR,int p){
    llg l=t[p].l,r=t[p].r;
    if(sL<=l&&r<=sR) return t[p].num;
    llg mid=(l+r)/2;
    llg res=1e18;
    if(sL<=mid) res=min(res,query(sL,sR,p*2));
    if(sR>mid) res=min(res,query(sL,sR,p*2+1));
    return res;
}
void f(){
    build(0,n,1);
    int left=1;
    for(int r=1;r<=n;r++){
        while(left<=r){
            llg ms=query(left-1,r-1,1);
            if(s[r]-ms>=k) left++;
            else break;
        }
        int cnt=r-left+1;
        if(cnt>0){
            bcnt[1]++;
            if(r-left+2<=n) bcnt[r-left+2]--;
        }
    }
    for(int len=1;len<=n;len++) bcnt[len]+=bcnt[len-1];
    for(int x=1;x<=n;x++) totb[x]=totb[x-1]+bcnt[x];
    return ;
}
llg solve(int x){
    llg tot=1LL*x*(2LL*n-x+1)/2;
    if(k<=0) return tot;
    return tot-totb[x];
}
int main(){
    freopen("tioj_interactive.in","r",stdin);
    freopen("tioj_interactive.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
	cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    if(k>0) f();
    cin>>q;
    while(q--){
        cin>>x;
        cout<<solve(x)<<endl;
    }
    return 0;
}