70ptsTLE求调

#include<bits/stdc++.h>
#define ls(x) x<<1
#define rs(x) x<<1|1
using namespace std;
const int N=2e5+7;
int n,q;
__int128 W;
__int128 arr[N];
__int128 sum[N<<2],tag[N<<2];
__int128 pw2[201];
__int128 bs[201];
void push_up(int p){
    sum[p]=sum[ls(p)]+sum[rs(p)];
}
void build(int p,int L,int R){
    if(L==R){
        sum[p]=arr[L];
        return ;
    }
    int mid=(L+R)>>1;
    build(ls(p),L,mid);
    build(rs(p),mid+1,R);
    push_up(p);
}
void addtag(int p,int pl,int pr,long long d){
    sum[p]+=(pr-pl+1)*d;
    tag[p]+=d;
}
void push_down(int p,int pl,int pr){
    if(tag[p]){
        int mid=(pl+pr)>>1;
        addtag(ls(p),pl,mid,tag[p]);
        addtag(rs(p),mid+1,pr,tag[p]);
    }
    tag[p]=0;
}
void edit(int p,int pl,int pr,int L,int R,long long d){
    if(L<=pl&&pr<=R){
        addtag(p,pl,pr,d);
        return ;
    }
    push_down(p,pl,pr);
    int mid=(pl+pr)>>1;
    if(L<=mid)edit(ls(p),pl,mid,L,R,d);
    if(mid+1<=R){
        edit(rs(p),mid+1,pr,L,R,d);
    }
    push_up(p);
}
int query(int p,int pl,int pr,__int128 W,__int128 times){
    if(pl==pr){
        if(sum[p]*pw2[times-1]<W)return pl;
        else return pl-1;
    }
    push_down(p,pl,pr);
    int mid=(pl+pr)>>1;
    if(W>sum[ls(p)]*pw2[times-1]){
        return query(rs(p),mid+1,pr,W-sum[ls(p)]*pw2[times-1],times);
    }else return query(ls(p),pl,mid,W,times);
}
__int128 gettimes(__int128 W){
    int l=0,r=60,mid;
    while(l<r){
        mid=(l+r+1)>>1;
        if(W>bs[mid]*sum[1]){
            l=mid;
        }else r=mid-1;
    }
    return l;
}
inline __int128 read(){
    __int128 x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')
            f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
inline void print(__int128 x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
        print(x / 10);
    putchar(x % 10 + '0');
}
int main(){ 
    pw2[0]=1;
    for(int i=1;i<=190;i++){
        pw2[i]=(__int128)2*pw2[i-1];
    }
    for(int i=0;i<=190;i++){
        bs[i]=pw2[i]-1;
    }
    scanf("%d%d%lld",&n,&q,&W);
    for(int i=1;i<=n;i++){
        arr[i]=read();
    }
    build(1,1,n);

    while(q--){
        int l,r;
        long long d;
        scanf("%d%d%lld",&l,&r,&d);
        edit(1,1,n,l,r,d);
        __int128 times=gettimes(W);
        __int128 nowW=W-bs[times]*sum[1];
        __int128 res=(__int128)query(1,1,n,nowW,times+1);
        print(times*n+res);
        printf("\n");
    }
    return 0;
}