题意

~~抱歉应该不能发~~

分析

最优解构造方法

不难证明，以下构造方案可以帮助我们构造一组可能的最优解：

选取一个编号 $i$，对于编号在 $1 \sim i-1$ 之间的每个 $a[i]$，尽量对 $a[i] \bmod c$ 部分使用代金券，对其他部分不使用代金券；对于编号在 $i+1 \sim n$ 之间的每个 $a[i]$，全部使用代金券；对于编号为 $i$ 的 $a[i]$，在满足上述约束条件下尽可能多地使用代金券。

考虑 $i$ 在取哪些值的时候可以满足上述构造方法：当我们对 $1 \sim i$ 实行贪心策略（对 $a[i] \bmod c$ 部分尽可能多地使用代金券）后留下的代金券数量 $cnt$ 大于 $sum = \sum_{x=i+1}^{n} a[x]$ 时 $i$ 为一个合法的取值。

容易发现对于 $1 \sim n$ 之间每个值是否能作为 $i$ 这一判断具备单调性，即若 $x$ 为 $i$ 的一个合法取值，那么 $x+1,~x+2,~\dots,~n$ 都能为 $i$ 的合法取值。同时当我们固定 $i$ 的取值后构造出来的最优解一定固定，并且 $i$ 越小，能够造出来的最优方案也越优。

考虑二分找出最小的符合要求的 $i$，对于这个找出的值构造出最优方案即可。

仔细观察上面所说的判断 $i$ 取值是否合法的方法，不易解决的是判断 $1 \sim x$ 部分使用贪心策略后留下来的代金券的数量。

使用线段树找出最优 $i$ 位置

我们考虑使用万能的线段树解决这个问题。在线段树的每个节点上我们保存对应区间的以下信息：

区间和 sum
对该区间顺序使用贪心策略后剩余的代金券数量 cnt
对该区间顺序使用贪心策略的总花费 cost
区间内所有在贪心策略中可以用代金券的部分的和 rest

最后一项可能不是很好理解，这里具体讲一下最后一项 rest 的含义：考虑在贪心策略中我们会对每个 $a[i] \bmod c$ 的部分使用尽可能多的代金券，rest 即为在区间内进行贪心策略后每个 $a[i] \bmod c$ 的剩余部分的和。（说“剩余”是因为在区间内执行贪心策略时已经为部分 $a[i] \bmod c$ 部分花费了一些代金券）

线段树节点信息合并方法也非常简单：

inline Node operator+(const Node& oth) const {
    return (Node){this->sum + oth.sum,
                  this->cnt + oth.cnt - min(cnt, oth.rest),
                  this->cost + oth.cost - min(cnt, oth.rest),
                  this->rest + oth.rest - min(cnt, oth.rest)};
}

合并过程采用了类似 CDQ 分治的思想，每次合并两个相邻区间的信息时计算左区间对右区间产生的贡献，在本题中即为使用左区间剩余的代金券抵消右区间尚未抵消并还能被抵消的部分。

接下来只需要在线段树上找出最小的使得 $[1,~i].cnt \ge [i+1,~n].sum$ 的 $i$ 即可。$O(lgn)$ 线段树上二分或者 $O(lgn^2)$ 二分 $i$ 并检验是否合法找出 $i$ 的复杂度都应该是本题所可以接受的。

判断 $i$ 位置的方案

根据构造方案，$1 \sim i-1$ 和 $i+1 \sim n$ 的构造方法都已确定，接下来考虑 $i$ 位置上的构造方法。

二分在 $i$ 位置上使用了几张代金券，检验 $1 \sim i-1$ 部分是否可以再拿出那么多张代金券以及 $i$ 位置使用那么多代金券后总剩余代金券量是否仍旧可以支持 $i+1 \sim n$ 部分的构造即可。

代码

时间复杂度 $O((n+q)lgn)$，在硬盘速度相当慢的本地机上跑民间数据每个点运行时长均不超过 1s。

/**
 * @author Macesuted (macesuted@qq.com)
 * @copyright Copyright (c) 2021
 */

#include <bits/stdc++.h>
using namespace std;

namespace io {

// fread

}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

#define maxn 300005

struct Node {
    long long sum, cnt, cost, rest;
    inline Node operator+(const Node& oth) const {
        return (Node){this->sum + oth.sum,
                      this->cnt + oth.cnt - min(this->cnt, oth.rest),
                      this->cost + oth.cost - min(this->cnt, oth.rest),
                      this->rest + oth.rest - min(this->cnt, oth.rest)};
    }
};

int n;
long long c;
long long a[maxn];

Node tree[maxn << 2];

void build(int p, int l, int r) {
    if (l == r) return tree[p].sum = tree[p].cost = a[l], tree[p].cnt = a[l] / c, tree[p].rest = a[l] % c, void();
    int mid = (l + r) >> 1;
    build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    return tree[p] = tree[p << 1] + tree[p << 1 | 1], void();
}
void update(int p, int l, int r, int qp, long long val) {
    if (l == r) return tree[p].sum = tree[p].cost = val, tree[p].cnt = val / c, tree[p].rest = val % c, void();
    int mid = (l + r) >> 1;
    qp <= mid ? update(p << 1, l, mid, qp, val) : update(p << 1 | 1, mid + 1, r, qp, val);
    return tree[p] = tree[p << 1] + tree[p << 1 | 1], void();
}
Node getAns(int p, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tree[p];
    int mid = (l + r) >> 1;
    Node answer = (Node){0, 0, 0, 0};
    if (ql <= mid) answer = answer + getAns(p << 1, l, mid, ql, qr);
    if (qr > mid) answer = answer + getAns(p << 1 | 1, mid + 1, r, ql, qr);
    return answer;
}

long long work(void) {
    int p = 1, l = 1, r = n;
    Node left = (Node){0, 0, 0, 0}, right = (Node){0, 0, 0, 0};
    while (l != r)
        if ((left + tree[p << 1]).cnt >= (tree[p << 1 | 1] + right).sum) {
            right = tree[p << 1 | 1] + right;
            p = p << 1, r = (l + r) >> 1;
        } else {
            left = left + tree[p << 1];
            p = p << 1 | 1, l = ((l + r) >> 1) + 1;
        }
    long long cnt = 0, rig = 0;
    if (l > 1) cnt = getAns(1, 1, n, 1, l - 1).cnt;
    if (l < n) rig = getAns(1, 1, n, l + 1, n).sum;
    long long vl = 0, vr = cnt + 1;
    while (vl + 1 < vr) {
        long long mid = (vl + vr) >> 1;
        (cnt + (a[l] - mid) / c - mid >= rig) ? vl = mid : vr = mid;
    }
    long long answer = a[l] - vl;
    if (l > 1) answer += getAns(1, 1, n, 1, l - 1).cost;
    return answer;
}

int main() {
    n = read<int>();
    int q = read<int>();
    c = read<long long>();
    for (register int i = 1; i <= n; i++) a[i] = read<long long>();
    build(1, 1, n);
    write(work()), putch('\n');
    while (q--) {
        int x = read<int>();
        update(1, 1, n, x, a[x] = read<long long>());
        write(work()), putch('\n');
    }
    return 0;
}