rt，自认为时间复杂度为qlogn，结果大样例跑了20s

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1000005;
const ll inf=2000000000000000005;
ll T,m,a[MAXN],pw[MAXN],gt[MAXN];
ll l,r,d,tmp;
ll t,s,tans,ts;
int n,cnt,lorz;
struct node{
	ll l,r,w,f;
}tree[4*MAXN];
inline ll read(){
	ll tmp=0;
	char t=getchar();
	while(t<'0'||t>'9')t=getchar();
	while(t>='0'&&t<='9'){
		tmp=(tmp<<1)+(tmp<<3)+(t^48);
		t=getchar();
	}
	return tmp;
}
void write(ll x){
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
void build(int k,int l,int r){
	tree[k].l=l,tree[k].r=r;
	if(l==r){
		tree[k].w=read();
		s+=tree[k].w;
		return ;
	}
	int mid=(l+r)>>1;
	build(k*2,l,mid);
	build(k*2+1,mid+1,r);
	tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
void down(int k){
	tree[k*2].f+=tree[k].f;
	tree[k*2+1].f+=tree[k].f;
	tree[k*2].w+=tree[k].f*(tree[k*2].r-tree[k*2].l+1);
	tree[k*2+1].w+=tree[k].f*(tree[k*2+1].r-tree[k*2+1].l+1);
	tree[k].f=0;
}
bool check(int k){
	if(tree[k].l==0)return 0;
	if(ts+(1ll<<cnt)*tree[k].w<t){
		ts+=(1ll<<cnt)*tree[k].w;
		lorz=tree[k].r;
		return 1;
	}
	if(tree[k].f)down(k);
	if(check(k*2)){
		if(check(k*2+1)){
			return 1;
		}
	}
	return 0;
}
void add(int k,int from,int to,int orz){
	if(tree[k].l>=from&&tree[k].r<=to){
		tree[k].w+=orz*(tree[k].r-tree[k].l+1);
		tree[k].f+=orz;
		return ;
	}
	if(tree[k].f)down(k);
	int mid=(tree[k].l+tree[k].r)>>1;
	if(from<=mid)add(k*2,from,to,orz);
	if(to>mid)add(k*2+1,from,to,orz);
	tree[k].w=tree[k*2].w+tree[k*2+1].w;
}
inline void getcnt(){
	cnt=log2(m/s+1);
	t=m-s*gt[cnt-1];
}
inline void solve(){
    tans=0,cnt=0;
    cin>>l>>r>>d;
	add(1,l,r,d);
	s+=(r-l+1)*d;
    getcnt(); 
    ts=0;
    check(1);
    if(t==0){
    	//printf("%lld\n",cnt*n-1);
    	write(cnt*n-1);
    	putchar('\n');
	}
    else {
    	//printf("%lld\n",cnt*n+lorz);
    	write(cnt*n+lorz);
    	putchar('\n');
	}
}
int main(){
    //freopen("wxyt4.in","r",stdin);
	//freopen("ANS.txt","w",stdout);
    cin>>n>>T>>m;
    pw[0]=1;
    for(int i=1;i;i++){
    	pw[i]=pw[i-1]*2;
    	if(pw[i]>inf)break;
	}
	gt[0]=1;
	for(int i=1;i;i++){
		gt[i]=gt[i-1]+pw[i];
		if(gt[i]>inf)break;
	}
    build(1,1,n);
    while(T--)solve();
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}