记录编号	530703	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	倚天剑的愤怒	最终得分	100
用户昵称	梦那边的美好ET	是否通过	通过
代码语言	C++	运行时间	14.858 s
提交时间	2019-04-29 11:59:36	内存使用	331.22 MiB

#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define LL long long
#define maxn 1000010
#define maxm 10000010
using namespace std;
LL a[maxn],f[maxn],x[maxn],ff[maxm],mind,kk,kkk,d,dd,minw;
LL lazy[maxn*4],mi1[maxn*4],wz1[maxn*4];
LL n,m,wz2[maxn*4],mi2[maxn*4],lin[maxm];
void pushdown(LL d){lazy[d*2]+=lazy[d];lazy[d*2+1]+=lazy[d];mi1[d*2]+=lazy[d];mi1[d*2+1]+=lazy[d];lazy[d]=0;}
void build(LL l,LL r,LL d){
	if(l==r){mi1[d]=f[l];mi2[d]=a[l];wz1[d]=wz2[d]=l;return;}
	LL m=(l+r)>>1;
	build(l,m,d*2);build(m+1,r,d*2+1);
	mi1[d*2]<=mi1[d*2+1]?wz1[d]=wz1[d*2]:wz1[d]=wz1[d*2+1];
	mi2[d*2]<=mi2[d*2+1]?wz2[d]=wz2[d*2]:wz2[d]=wz2[d*2+1];
	mi1[d]=min(mi1[d*2],mi1[d*2+1]);
	mi2[d]=min(mi2[d*2],mi2[d*2+1]);
	return;
}
void putit1(LL x,LL y,LL z,LL l,LL r,LL d){//区间加,维护区间min和min的位置],维护f[i] 
	if(x<=l&&y>=r){mi1[d]+=z;lazy[d]+=z;return;}
	if(lazy[d])pushdown(d);
	LL m=(l+r)>>1;
	if(x<=m)putit1(x,y,z,l,m,d*2);
	if(y>m)putit1(x,y,z,m+1,r,d*2+1);
	mi1[d*2]<=mi1[d*2+1]?wz1[d]=wz1[d*2]:wz1[d]=wz1[d*2+1];
	mi1[d]=min(mi1[d*2],mi1[d*2+1]);
	return;
}
void putit2(LL x,LL l,LL r,LL d){//单点清零。维护区间min，维护a[i] 
	if(l==r){mi2[d]=0;return;}
	LL m=(l+r)>>1;
	if(x<=m)putit2(x,l,m,d*2);
	else putit2(x,m+1,r,d*2+1);
	mi2[d*2]<=mi2[d*2+1]?wz2[d]=wz2[d*2]:wz2[d]=wz2[d*2+1];
	mi2[d]=min(mi2[d*2],mi2[d*2+1]);
	return;
}
LL findit(LL x,LL y,LL l,LL r,LL d){
	//mind-a[i]（前缀min，即mi2[d]）单调递增，f[i-1]（前缀和的前缀min,即mi1[d]）单调递减 
	//x=a[l-1],y=f[l-1] 
	if(l==r)return mind-min(a[l],x)>=y?l:-1;
	if(lazy[d])pushdown(d);
	LL m=(l+r)>>1;
	LL xx=min((LL)mi2[d*2],x),yy=min(y,mi1[d*2]);
	LL xxx=min(xx,a[m+1]);//xx=a[m+1],yy=f[m] 
	if(mind-xxx>=yy){//m+1合法?
		int kk=findit(x,y,l,m,d*2);
		return kk==-1?m+1:kk;
	}
	return findit(xx,yy,m+1,r,d*2+1);
}
LL find1(LL x,LL l,LL r,LL d){//求f[x] 
	if(x==0)return 1e18; 
	if(r<=x)return mi1[d];if (lazy[d])pushdown(d);
	LL m=(l+r)>>1;
	if(x<=m)return find1(x,l,m,d*2);
	return min(find1(x,m+1,r,d*2+1),mi1[d*2]);
}
LL find2(LL x,LL l,LL r,LL d){//求a[x] 
	if(r<=x)return mi2[d];
	LL m=(l+r)>>1;
	if(x<=m)return find2(x,l,m,d*2);
	return min(find2(x,m+1,r,d*2+1),(LL)mi2[d*2]);
}
LL find3(LL x,LL l,LL r,LL d){//求a[x]的位置 
	if(r<=x)return wz2[d];
	LL m=(l+r)>>1;
	if(x<=m)return find3(x,l,m,d*2);
	int k=find3(x,m+1,r,d*2+1);
	return a[k]>=mi2[d*2]?wz2[d*2]:k;
}
void check(LL x){
	if(x<1||x>n)return;
	LL xx=find1(x-1,1,n,1),yy=mind-find2(x,1,n,1);
	if(!kk)kk=x,kkk=min(xx,yy);
	else if(min(xx,yy)>kkk)kkk=min(xx,yy),kk=x;
	return;
}
bool pd(LL a,LL b){return x[a]>x[b];}
int main(){
	freopen("angryy.in","r",stdin);
	freopen("angryy.out","w",stdout);
	scanf("%lld%lld",&n,&m);
	for(LL i=1;i<=n;i++)scanf("%lld",&a[i]),f[i]=f[i-1]+a[i];
	for(LL i=1;i<=m;i++)scanf("%lld",&x[i]),lin[i]=i;
	sort(lin+1,lin+1+m,pd);
	build(1,n,1);d=1;mind=-mi1[1];
	while(x[lin[d]]>=mind&&d<=m)d++;
	for(LL i=1;i<=n&&d<=m;i++){
		mind=mi1[1];minw=wz1[1];
		dd=findit(1e18,1e18,1,n,1);//找到第一个f[i-1]小于等于mind-a[i]的位置
		if(dd==-1)dd=n; 
		dd=min(dd,minw);kk=0;
		check(dd);check(dd-1);check(dd+1);
		kk=find3(kk,1,n,1);
		putit1(kk,n,-a[kk],1,n,1);
		putit2(kk,1,n,1);
		a[kk]=0;mind=-mi1[1];
		while(x[lin[d]]>=mind&&d<=m)ff[lin[d]]=i,d++;
		if(d>m)break;
	}
	for(LL i=1;i<=m;i++)printf("%lld\n",ff[i]);
	return 0;
}