$提交记录$

输入

6 4 75
9 1 4 5 1 4
1 1 1
3 5 3
3 5 1
3 5 3

输出

11
9
9
8

Code:

#include <cstdio>
#include <cctype>
#include <algorithm>

char *p1, *p2, buf[100000];
#define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ )

using namespace std;

typedef long long ll;

const int N = 200000 + 10;

ll n, m, k;
ll w[N];
struct Node
{
    int l, r;
    ll sum, add;
}t[N << 2];

inline void pushup(register int u)
{
    t[u].sum = t[u << 1].sum + t[u << 1 | 1].sum;
}

inline void pushdown(register int u)
{
    register Node &root = t[u], &left = t[u << 1], &right = t[u << 1 | 1];
    if (root.add)
    {
        left.add += root.add, left.sum += (ll)(left.r - left.l + 1) * root.add;
        right.add += root.add, right.sum += (ll)(right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}

inline void build(register int u, register int l, register int r)
{
    if (l == r)
        t[u] = {l, r, w[r], 0};
    else
    {
        t[u] = {l, r};
        register int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

inline ll query(register int u, register int l, register int r)
{
    if (t[u].l >= l && t[u].r <= r)
        return t[u].sum;
        
    pushdown(u);
    register ll sum = 0;
    register int mid = t[u].l + t[u].r >> 1;
    if (l <= mid)
        sum += query(u << 1, l, r);
    if (r > mid)
        sum += query(u << 1 | 1, l, r);
        
    return sum;
}

inline void modify(register int u, register int l, register int r, register ll d)
{
    if (t[u].l >= l && t[u].r <= r)
    {
        t[u].sum += (ll)(t[u].r - t[u].l + 1) * d;
        t[u].add += d;
    }
    else
    {
        pushdown(u);
        int mid = t[u].l + t[u].r >> 1;
        if (l <= mid)
            modify(u << 1, l, r, d);
        if (r > mid)
            modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

inline int dfs(register int u, register int l, register int r, register ll cnt, register ll w)
{
    if (l == r)
        return l;
    
    pushdown(u);
    register int mid = l + r >> 1;
    if (w >= t[u << 1].sum * cnt)
        return dfs(u << 1 | 1, mid + 1, r, cnt, w - t[u << 1].sum * cnt);
    return dfs(u << 1, l, mid, cnt, w);
}

template<typename T> inline void read(register T &qwq)
{
    register T x = 0, f = 1;
    register char ch = nc();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = nc();
    }
    while (isdigit(ch))
        x = (x << 1) + (x << 3) + (ch ^ 48), ch = nc();
    qwq = x * f;
    return;
}

template<typename T> inline void write(register T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
    return;
}

int main()
{
    read(n), read(m), read(k);
    
    for (register int i = 1; i <= n; i ++ )
        read(w[i]);
        
    build(1, 1, n);
    
    register int l, r, ans;
    register ll d, cnt, res, sum;
    while (m -- )
    {
        read(l), read(r), read(d);
        modify(1, l, r, d);
        
        cnt = 1, res = k, sum = query(1, 1, n), ans = 0;
		while (true)
		{
			if (res <= sum) 
			    break;
			res -= sum;
			sum <<= 1;
			ans += n;
			cnt <<= 1;
		}
		write(ans + dfs(1, 1, n, cnt, res) - 1), puts("");
    }
        
    return 0;
}