이 문제는 주로 자료구조를 다루며, O(n log²n) 시간 복잡도를 가지는 이진 인덱스 트리와 이분 탐색 조합이 O(n log n)의 세그먼트 트리 이분 탐색보다 빠르다는 점을 보여줍니다. 세그먼트 트리는 상수 최적화가 필요할 정도로 20ms 차이로 시간 초과가 발생합니다.

공식을 통해 k 라운드(모두 사용) 후 체력이 0이 되는 지점을 이분 탐색으로 찾을 수 있습니다. 그 다음 k-1을 사용하여 마지막 라운드에서 실제로 사용되는 양을 찾습니다. 이 과정에서 합계와 이분 탐색이 필요하므로 세그먼트 트리 이분 탐색 또는 이진 인덱스 트리 합계 계산과 이분 탐색을 사용할 수 있습니다.

이진 인덱스 트리 + 이분 탐색

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>

using namespace std;

typedef long long LL;

const int MAX = 200010;

LL n, m, w;
LL fenwick[MAX], fenwickSum[MAX];
LL values[MAX];


LL read()
{
    LL x = 0, sign = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if(ch == '-' )
            sign = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch -'0', ch = getchar();
    return x * sign;
}

int lowbit(int x)
{
    return x & -x;
}

void update(LL fenw[], int pos, LL val)
{
    for (int i = pos; i <= n; i += lowbit(i)) fenw[i] += val;
}

void rangeUpdate(int left, int right, LL val)
{
    update(fenwick, left, val);
    update(fenwick, right + 1, -val);
    update(fenwickSum, left, left * val);
    update(fenwickSum, right + 1, -(right + 1) * val);
}


LL query(LL fenw[], int pos)
{
    LL res = 0;
    for (int i = pos; i; i -= lowbit(i)) res += fenw[i];
    return res;
}

LL rangeQuery(int pos)
{
    LL a = query(fenwick, pos), b = query(fenwickSum, pos);
    return (__int128)a * (pos + 1) - b;
}

LL findRounds(LL total, LL current)
{
    LL left = 0, right = 61;
    
    while (left < right)
    {
        LL mid = left + right >> 1;
        if ((__int128)current * ((1ll << mid) - 1) >= total) right = mid;
        else left = mid + 1;
    }
    return left;
}

LL findPosition(LL target, LL rounds)
{
    int left = 0, right = n;
    
    while (left < right)
    {
        int mid = left + right >> 1;
        if ((__int128)rangeQuery(mid) * (1ll << rounds) >= target) right = mid;
        else left = mid + 1;
    }
    return left;
}

int main()
{
    cin >> n >> m >> w;
    
    for (int i = 1; i <= n; i ++ )
    {
        values[i] = read();
        update(fenwick, i, values[i] - values[i - 1]);
        update(fenwickSum, i, 1ll * i * (values[i] - values[i - 1]));
    }
    
    LL total = rangeQuery(n);
    while (m -- )
    {
        LL l, r, d;
        l = read();
        r = read();
        d = read();
        rangeUpdate(l, r, d);
        total += (r - l + 1) * d;
        LL result = total, answer = 0;
        LL rounds = findRounds(w, result) - 1;
        answer = rounds * n; 
        answer += findPosition(w - result * ((1ll << rounds) - 1), rounds) - 1;
        printf("%lld\n", answer);
    }
    
    return 0;
}

세그먼트 트리 이분 탐색

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <ctime>

using namespace std;

typedef long long LL;

const int MAX = 200010;

LL n, m, w;
LL arr[MAX];

struct Node 
{
    int left, right;
    __int128 sum, lazy;
} tree[MAX * 4];

LL read()
{
    LL x = 0, sign = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if(ch == '-' )
            sign = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        x = x * 10 + ch -'0', ch = getchar();
    return x * sign;
}


void merge(Node &parent, Node &left, Node &right)
{
    parent = {left.left, right.right, left.sum + right.sum};
}

void merge(int node)
{
    merge(tree[node], tree[node << 1], tree[node << 1 | 1]);
}

void apply(Node &node, LL val)
{
    node.sum += (node.right - node.left + 1) * val;
    node.lazy += val;
}

void push(int node)
{
    apply(tree[node << 1], tree[node].lazy);
    apply(tree[node << 1 | 1], tree[node].lazy);
    tree[node].lazy = 0;
}

void build(int node, int left, int right)
{
    if (left == right) tree[node] = {left, right, arr[left]};
    else
    {
        tree[node] = {left, right};
        int mid = left + right >> 1;
        build(node << 1, left, mid);
        build(node << 1 | 1, mid + 1, right);
        merge(node);
    }
}

void update(int node, int left, int right, int val)
{
    if (left <= tree[node].left && tree[node].right <= right) apply(tree[node], val);
    else
    {
        push(node);
        int mid = tree[node].left + tree[node].right >> 1;
        if (left <= mid) update(node << 1, left, right, val);
        if (right > mid) update(node << 1 | 1, left, right, val);
        merge(node);
    }
}

LL query(int node, int left, int right)
{
    if (left <= tree[node].left && tree[node].right <= right) return tree[node].sum;
    else
    {
        push(node);
        int mid = tree[node].left + tree[node].right >> 1;
        LL sum = 0;
        if (left <= mid) sum += query(node << 1, left, right);
        if (right > mid) sum += query(node << 1 | 1, left, right);
        return sum;
    }
}

LL findLeft(int node, int left, int right, LL k, LL target, LL prefix)
{
    if (tree[node].left == tree[node].right) 
    {
        if ((__int128)(tree[node].sum + prefix) * k < target) return -1;
        return tree[node].left;
    }
    else if (left <= tree[node].left && tree[node].right <= right)
    {
    	push(node);
        if ((__int128)(tree[node << 1].sum + prefix) * k >= target) return findLeft(node << 1, left, right, k, target, prefix);
        else return findLeft(node << 1 | 1, left, right, k, target, prefix + tree[node << 1].sum);
    }
}

LL findRounds(LL total, LL current)
{
    LL left = 0, right = 61;
    
    while (left < right)
    {
        LL mid = left + right >> 1;
        if ((__int128)current * ((1ll << mid) - 1) >= total) right = mid;
        else left = mid + 1;
    }
    return left;
}

signed main()
{
    cin >> n >> m >> w;
    
    for (int i = 1; i <= n; i ++ )
    {
        arr[i] = read();
    }
    
    build(1, 1, n);
    LL total = query(1, 1, n);
    while (m -- )
    {
        LL l, r, d;
        l = read();
        r = read();
        d = read();
        update(1, l, r, d);
        total += 1ll * (r - l + 1) * d;
        LL result = total, answer = 0;
        LL rounds = findRounds(w, result) - 1;
        answer = rounds * n; 
        answer += findLeft(1, 1, n, (1ll << rounds), w - result * ((1ll << rounds) - 1), 0) - 1;
        printf("%lld\n", answer);
    }
    
    return 0;
}