BIT+二分 20pts 求调

#include<bits/stdc++.h>
#define ll long long
using namespace std;
#define lowbit(x) ((x) & (-x))
ll hits[200005], n;

ll t1[200005], t2[200005];

void add(ll k, ll v) {
    int v1 = k * v;
    while (k <= n) {
        t1[k] += v, t2[k] += v1;
        k += lowbit(k);
    }
}

ll getsum(ll *t, ll k) {
    ll ret = 0;
    while (k) {
        ret += t[k];
        k -= lowbit(k);
    }
    return ret;
}

void add1(ll l, ll r, ll v) {
    add(l, v), add(r + 1, -v);
}

ll getsum1(ll r) {
    ll l=1;
    return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
         (getsum(t2, r) - getsum(t2, l - 1));
}

ll binary(ll x, ll mult){    // 找到其中第一个 >= x 的位置，mult 为倍数
    ll res = 0, start = 1, end = n;
    
    while (start <= end) {
        ll mid = start + ((end - start) >> 1);
        if(getsum1(mid) >= x/mult){
            res = mid;
            end = mid - 1;
        } else {
            start = mid + 1;
        }
    }

    return res;
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    auto start = std::chrono::high_resolution_clock::now();

    ll q,W,sum = 0;
    cin>>n>>q>>W;

    for(ll i=1;i<=n;i++)    cin>>hits[i], sum+= hits[i], add1(i, i, hits[i]);
    ll total = sum;

    for(ll i=1;i<=q;i++){
        ll a,b,enhance,score = 0;
        cin>>a>>b>>enhance;

        // fronts[a] += enhance;
        // fronts[b+1] -= enhance;
        // 差分
        add1(a, b, enhance);

        total += (b-a+1) * enhance;   // 无加倍 的分数
        ll round = 1, k = 1;
        for(ll tempW = W;;){
            tempW -= total * k;
            if(tempW/(k*2) <= total)  break;
            k *= 2, round ++;
        };
        k *= 2;

        score = round * n;

        ll pos = 0;

        // for(double lW = (W - total * (k - 1)); lW > 0;){
        //     now += fronts[pos];
        //     lW -= (hits[pos++] + now) * (k);
        // }
        pos = binary(W - total * (k-1), k);
        // cout<<"==";
        // for(int i=1;i<=n;i++)   cout<<ask(i) - ask(i-1)<<" ";
        // for(int i=1,effect = 0;i<=n;i++){
        //     cout<< getsum1(i) - getsum1(i-1)<<" ";
        // }
        // cout<<" -->";
        // cout<<pos<<"rnd ==) => ";
        cout<<pos + score - 1<<"\n";
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cerr << "time: " << duration.count() << " ms" << std::endl;
}

/*
6 1 75
9 1 4 5 1 4
1 1 1

re: 11
*/