线段树上二分求调

#include<bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int N = 2e5+10;
const int INF = 2e9;
const int mod = 1e9+7;

int n , q, W , tree[N<<2] , a[N],tag[N<<2];

inline int read(){
    int x = 0 , f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){if(c=='-')f=-1;c=getchar();}
    while(c >='0' && c <='9') x = (x << 1) + (x << 3) + (c ^ 48),c = getchar();
    return x * f;
}

void write(int x){
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

inline void pushdown(int pos,int l,int r){
    if(!tag[pos]) return;
    re int mid = (l + r) >> 1;
    tag[pos<<1] += tag[pos];
    tag[pos<<1|1] += tag[pos];
    tree[pos<<1] += (mid - l + 1) * tag[pos];
    tree[pos<<1|1] += (r - mid) * tag[pos];
    tag[pos] = 0;
}

void build(int pos,int l,int r){
    if(l == r){
        tree[pos] = a[l];
        return;
    }
    re int mid = (l + r) >> 1;
    build(pos<<1,l,mid);
    build(pos<<1|1,mid+1,r);
    tree[pos] = tree[pos << 1] + tree[pos << 1 | 1];
}

void update(int pos,int l,int r,int x,int y,int val){
    if(x <= l && r <= y){
        tag[pos] += val;
        tree[pos] += (r - l + 1) * val;
        return;
    }
    int mid = (l + r) >> 1;
    pushdown(pos,l,r);
    if(x <= mid) update(pos<<1,l,mid,x,y,val);
    if(mid < y) update(pos<<1|1,mid+1,r,x,y,val);
    tree[pos] = tree[pos<<1] + tree[pos<<1|1];
}

int query(int pos,int l,int r,int x,int y){
    if(x <= l && r <= y) return tree[pos];
    int mid = (l + r)  >> 1,res = 0;
    pushdown(pos,l,r);
    if(x<=mid) res += query(pos<<1,l,mid,x,y);
    if(mid < y) res += query(pos<<1|1,mid+1,r,x,y);
    return res;
}

int rk(int pos,int l,int r,int x,int sum,int cnt){
    if(l == r) {
        if((tree[pos] + sum)*cnt >= x) return l-1;
        return l;
    }
    int mid = (l + r) >> 1;
    if((tree[pos<<1] + sum) * cnt >= x) return rk(pos<<1,l,mid,x,sum,cnt);
    return rk(pos<<1|1,mid+1,r,x,sum + tree[pos<<1],cnt);
}

signed main(){
    n = read(),q = read(), W = read();
    for(int i = 1; i <= n; i++) a[i] = read();
    build(1,1,n);
    while(q--){
        int x , y, d;
        x = read(),y = read(),d = read();
        update(1,1,n,x,y,d);
        int sum = query(1,1,n,1,n),tmp = W,cnt = 1,ans = 0;
        while(tmp > sum) tmp -= sum,sum *= 2,cnt *= 2,ans += n; 
        write(ans+rk(1,1,n,tmp,0,cnt));
        puts("");
    }   
    return 0;
}