提交记录

#include<bits/stdc++.h>
#define lt root<<1
#define rt root<<1|1
using namespace std;
const int N=2e5+5;
int n,q;
long long tree[4*N],lazy[4*N],w;
void up(int root) 
{
	tree[root]=tree[lt]+tree[rt];
}
void down(int root,int l,int r)
{
	int mid=l+r>>1;
	lazy[lt]+=lazy[root];
	lazy[rt]+=lazy[root];
	tree[lt]+=(mid-l+1)*lazy[root];
	tree[rt]+=(r-mid)*lazy[root];
	lazy[root]=0;
}
void build(int root,int l,int r)
{
	if(l==r)
	{
		scanf("%lld",&tree[root]);
		return ;
	} 
	int mid=l+r>>1;
	build(lt,l,mid);
	build(rt,mid+1,r);
	up(root);
}
void updata(int root,int l,int r,int l1,int r1,int x)
{
	if(r1<l || r<l1) return;
	if(l1<=l && r<=r1)
	{
		tree[root]+=(r-l+1)*x;
		lazy[root]+=x;
		return;
	}
	down(root,l,r);
	int mid=l+r>>1;
	updata(lt,l,mid,l1,r1,x);
	updata(rt,mid+1,r,l1,r1,x);
	up(root);
}
long long getsum(int root,int l,int r,int l1,int r1)
{
	if(l1<=l && r<=r1) return tree[root];
	if(r<l1 || r1<l) return 0ll;
	down(root,l,r);
	int mid=l+r>>1;
	return getsum(lt,l,mid,l1,r1)+getsum(rt,mid+1,r,l1,r1);
}
int getans(long long xl)
{
	long long cnt=1,lun=0,k=getsum(1,1,n,1,n);
	for(;;)
	{
		if(xl>k*cnt) {xl-=k*cnt;cnt=cnt*2;lun++;}
		else break;
	}
	//printf("%d %lld %lld ",w,k,lun);
	int l=1,r=n,ans=0;
	while(l+1<r)
	{
		int mid=l+r>>1;
		if(getsum(1,1,n,1,mid)*cnt<xl) l=mid;
		else r=mid;
	}
	printf("%lld\n",l+lun*n);
}
int main()
{
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout); 
	scanf("%d%d%lld",&n,&q,&w);
	build(1,1,n);
	for(int i=1;i<=q;i++)
	{
		int l,r,d;
		scanf("%d%d%d",&l,&r,&d);
		updata(1,1,n,l,r,d);
		getans(w);
	}	
	return 0;
} 

longlong开两个 $8 \times 10^5$ 的为什么会MLE啊？线段树也没问题。。。