#include<bits/stdc++.h>
typedef long long int64;
typedef __int128 int128;
namespace mainCode
{
	using namespace std;
	const int N=2e5+1;
	int n,q,ans;
	int64 w,now,p,a[N],ad[N<<2];
	int128 sum[N<<2];
	void pushup(int k)
	{
		sum[k]=sum[k<<1]+sum[k<<1|1];
	}
	void build(int k,int l,int r)
	{
		if (l==r)
		{
			sum[k]=a[l];
			return;
		}
		int mid=(l+r)>>1;
		build(k<<1,l,mid);
		build(k<<1|1,mid+1,r);
		pushup(k);
	}
	void add(int k,int l,int r,int x)
	{
		ad[k]+=x,sum[k]+=x*(r-l+1);
	}
	void pushdown(int k,int l,int r,int mid)
	{
		if (!ad[k]) return;
		add(k<<1,l,mid,ad[k]);
		add(k<<1|1,mid+1,r,ad[k]);
		ad[k]=0;
	}
	void update(int k,int l,int r,int x,int y,int z)
	{
		if (r<x||l>y) return;
		if (l>=x&&r<=y)
		{
			add(k,l,r,z);
			return;
		}
		int mid=(l+r)>>1;
		pushdown(k,l,r,mid);
		if (mid>=x) update(k<<1,l,mid,x,y,z);
		if (mid<y) update(k<<1|1,mid+1,r,x,y,z);
		pushup(k);
	}
	void search()
	{
		int k=1,l=1,r=n,mid;
		while (l<=r)
		{
			if (sum[k]*p<now)
			{
				ans+=r-l+1;
				break;
			}
			if (l==r&&sum[k]*p>=now) break;
			mid=(l+r)>>1;
			pushdown(k,l,r,mid);
			if (sum[k<<1]*p<now) ans+=mid-l+1,now-=sum[k<<1]*p,k=k<<1|1,l=mid+1;
			else k<<=1,r=mid;
		}
	}
	void main()
	{
		cin>>n>>q>>w;
		for (int i=1;i<=n;i++)
		  cin>>a[i];
		build(1,1,n);
		int l,r,d;
		int128 s;
		while (q--)
		{
			cin>>l>>r>>d;
			update(1,1,n,l,r,d);
			s=sum[1],now=w,ans=0,p=1;
			while (now>s*p) ans+=n,now-=s*p,p<<=1;
			if (now==s*p) ans+=n-1;
			else search();
			cout<<ans<<"\n";
		}
	}
}
signed main()
{
//	freopen("wxyt4.in","r",stdin);
//	freopen("wxyt.out","w",stdout);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	mainCode::main();
	return 0;
}

评测记录

自己之前在线段树上写Rank什么的就经常出问题。

样例四没过，查了一下发现偏差很小在个位数