理论 $O（qlog^2n）$ 实际上被卡常

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#define N 200010

using namespace std;
typedef __int128 LL;

LL read()
{
	LL xx=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){xx=xx*10+ch-'0';ch=getchar();}
	return xx*f;
}
void write(LL xx)
{
	if(xx<0){xx=-xx;putchar('-');}
	if(xx>9) write(xx/10);
	putchar(xx%10+'0');
	return;
}
LL n,q,W,t[N*4],lazy[N*4],SUM;
void build(int k,int l,int r)
{
	if(l==r)
	{
		t[k]=read();
		SUM+=t[k];
		return;
	}
	int mid=(l+r)/2;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	t[k]=t[k*2]+t[k*2+1];
	return;
}
void Down(int k,LL l,LL r)
{
	lazy[k*2]+=lazy[k];
	lazy[k*2+1]+=lazy[k];
	LL mid=(l+r)/2;
	t[k*2]=t[k*2]+lazy[k]*(mid-l+1);
	t[k*2+1]=t[k*2+1]+lazy[k]*(r-mid);
	lazy[k]=0;
	return;
}
void change(int k,int l,int r,int gl,int gr,LL num)
{
	if(l>gr||r<gl) return;
	if(l>=gl&&r<=gr)
	{
		t[k]+=num*(r-l+1);
		lazy[k]+=num;
		return;
	}
	Down(k,(LL)l,(LL)r);
	int mid=(l+r)/2;
	change(k*2,l,mid,gl,gr,num);
	change(k*2+1,mid+1,r,gl,gr,num);
	t[k]=t[k*2]+t[k*2+1];
	return;
}
LL sum,ans;
void query(int k,int l,int r,int gl,int gr)
{
	if(l>gr||r<gl) return;
	if(l>=gl&&r<=gr)
	{
		sum+=t[k];
		return;
	}
	Down(k,(LL)l,(LL)r);
	int mid=(l+r)/2;
	query(k*2,l,mid,gl,gr);
	query(k*2+1,mid+1,r,gl,gr);
	return;
}
LL ksm(LL k,LL mi)
{
	LL xx=1;
	while(mi>0)
	{
		if(mi%2==1) xx=xx*k;
		k=k*k;
		mi=mi/2;
	}
	return xx;
}
void Start()
{
	n=read();q=read();W=read();
	build(1,1,n);
	LL l,r,d;
	while(q--)
	{
		l=read();r=read();d=read();
		SUM+=(r-l+1)*d;
		change(1,1,n,l,r,d);
		int cnt_l=0,cnt_r=64;
		while(cnt_l<cnt_r)
		{
			int cnt_mid=(cnt_l+cnt_r)/2;
			LL now_mid=ksm(2,cnt_mid)-1;
			if(SUM*now_mid>=W) cnt_r=cnt_mid;
			else cnt_l=cnt_mid+1;
		}
		ans=n*(cnt_l-1);
		LL now_life=W-(ksm(2,cnt_l-1)-1)*SUM;
		LL st=ksm(2,cnt_l-1);
		cnt_l=1;cnt_r=n;
		while(cnt_l<cnt_r)
		{
			sum=0;
			int cnt_mid=(cnt_l+cnt_r)/2;
			query(1,1,n,1,cnt_mid);
			if(st*sum>=now_life) cnt_r=cnt_mid;
			else cnt_l=cnt_mid+1;
		}
		write(ans+cnt_l-1);
		printf("\n");
	}
	return;
}
int main()
{
	Start();
	return 0;
}