The sol of 《youyou 的垃圾桶》

思路

正解貌似是差分，但可以比较无脑地用线树上二分来做（乱搞的快感）

解题方法

用线段树处理每次强化的攻击力； 先预处理出前缀和，然后先用攻击力不断翻倍，用总生命值去减，剩下的不能用整段处理的生命值去二分地求前缀和（记得要乘上倍数）。
要在线段树上二分，这样是 $O(q*log(n))$ 不然就有两只 $log$。
注意，要写快读，因为我写的线段数过于丑陋，被卡常了。

时间复杂度:

$O(q*log(n))$

Code

#include<bits/stdc++.h>
#define Ying using
#define AK namespace 
#define IOI std;
Ying AK IOI
#define int long long
#define ls (p<<1)
#define rs (p<<1|1)
#define len(x) (t[x].r-t[x].l+1)
#define mid ((l+r)>>1)
#define FOR(i,_l,_r) for(int i=_l;i<=_r;i++)
const int N=2e5+5;
#define il inline
il int read(){
    int x=0;
    int f=1;
    char c;
    c=getchar_unlocked();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar_unlocked();
    }
    return x*f;
}
il void print(int x){
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
int n,q,W;
int a[N];
struct node{
    int l,r,sum,tag;
}t[N<<2];
void up(int p){
    t[p].sum=t[ls].sum+t[rs].sum;
}
void Build(int p,int l,int r){
    t[p].l=l;t[p].r=r;
    if(l==r){
        t[p].sum=a[l];
        return;
    }
    Build(ls,l,mid);
    Build(rs,mid+1,r);
    up(p);
}
void spread(int p){
    if(!t[p].tag) return;
    int d=t[p].tag;
    t[ls].sum+=len(ls)*d;
    t[rs].sum+=len(rs)*d;
    t[ls].tag+=d;
    t[rs].tag+=d;
    t[p].tag=0;
}
void change(int p,int L,int R,int v){
    int l=t[p].l;
    int r=t[p].r;
    if(L<=l&&r<=R){
        t[p].sum+=v*len(p);
        t[p].tag+=v;
        return;
    }
    spread(p);
    if(L<=mid) change(ls,L,R,v);
    if(R>mid) change(rs,L,R,v);
    up(p);
}
int query(int p,int L,int R){
    int l=t[p].l;
    int r=t[p].r;
    if(L<=l&&r<=R)  return t[p].sum;
    spread(p);
    int ans=0;
    if(L<=mid) ans+=query(ls,L,R);
    if(R>mid) ans+=query(rs,L,R);
    return ans;
}
int Q(int p,int l,int r,int w,int x){
    if(l==r) return l-1;
    spread(p);
    if(t[ls].sum*x>=w) return Q(ls,l,mid,w,x);
    else return Q(rs,mid+1,r,w-t[ls].sum*x,x);
}
signed main(){
    #ifndef ONLINE_JUDGE
    freopen("wxyt.in","r",stdin);
    freopen("wxyt.out","w",stdout);
    #endif 
    ios::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    n=read();q=read();W=read();
    FOR(i,1,n) a[i]=read();
    Build(1,1,n);
    while(q--){
        int cnt=0;
        int t=0;
        int w=W;
        int x,y,k;
        x=read();y=read();k=read();
        change(1,x,y,k);
        int sum=query(1,1,n);
        while(w>=sum){
            w-=sum;
            sum<<=1;
            cnt+=n;
            t++;
        }
        if(!w){
            print(cnt-1);
            puts("");
            continue;
        }
        print(Q(1,1,n,w,(1LL<<t))+cnt);
        puts("");
    }
    return 0;
}