题目:https://www.luogu.com.cn/problem/P11217

我用的前缀和与二分做的,感觉和线段树没差多少,但tle,求助，以下是我的代码

#include<bits/stdc++.h>
#define For(i,j,k) for(int i=j;i<k;i++)
#define LL long long
using namespace std;
int n,q;
const int N=2e5;
LL W,a[N],A[N];
void sum(){
	A[0]=a[0];
	For(i,1,n){
		A[i]=A[i-1]+a[i];
	}
}
void strongthen(LL l,LL r,LL d){
	For(i,l,n){
		if(i<=r)A[i]+=(i-l+1)*d;
		else A[i]+=(r-l+1)*d;
	}
}
void battle(){
	int Q=__lg(W/A[n-1]+1);
	int re=W-(1LL<<Q-1)*A[n-1];
	int left=0,right=n-1,mid;
	while(left<=right){
		mid=left+(right-left)/2;
		if((2^Q-1)*A[mid]>re)left=mid-1;
		else if((2^Q-1)*A[mid]<re)right=mid+1;
		else{
			left=mid;
			break;
		}
	}
	cout<<Q*n+left<<endl;
}
int main(){
	cin>>n>>q>>W;
	For(i,0,n)cin>>a[i];
	sum();
	For(i,0,q){
		LL l,r,d;
		cin>>l>>r>>d;
		strongthen(l,r,d);
		battle();
	}
	return 0;
}