| 比赛 |
期末考试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;
}