本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-06 20:56:47

传送门： C. Watching Fireworks is Fun

upd：这题的slope trick（现在才知道这个优化原来叫这个）和 CF1534G 一模一样，而且只用两个优先队列维护即可，比我当时写的一坨splay简洁多了。

考虑记 $f_{i,j}$ 为第 $i$ 个烟花燃放后，当前位置在 $j$ 时的最大快乐值，转移显然：

$$ f_{i,j} = \max_{k = - d(t_i-t_{i-1})}^{d(t_i-t_{i-1})}\{f_{i-1,j+k} \} + b_i- |a_i-j| $$

观察转移式，$f_i$ 是由 $f_{i-1}$ 加上一个关于 $j$ 的函数 $b_i-|a_i-j|$ 得到的，注意到 $b_i-|a_i-j|$ 是上凸函数，不妨猜测 $f_i$ 也是上凸函数，事实上使用归纳法非常容易证明—— $\max_{k = - d(t_i-t_{i-1})}^{d(t_i-t_{i-1})}\{f_{i-1,j+k} \}$ 相当于将 $f_{i,j}$ 的图像从最高点处分为左右两半，左半边整体向左平移 $d(t_i-t_{i-1})$，右半边整体向右平移 $d(t_i-t_{i-1})$，最后再用一条斜率为 $0$ 的线段从断点处将两部分连接起来，很明显若 $f_{i-1}$ 是上凸函数，那么变换后依然保持上凸，$f_i$ 就等于两个上凸函数相加，必然还是上凸函数。

用平衡树维护函数上的拐点，即可在 $O(m \log m)$ 时间内解决本问题。

代码：

#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define ll __int128
#define pb push_back
#define mp make_pair
using namespace std;

const int MAXN = 4e5+5;
const int Mod = 998244353;

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

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

void write(ll x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) write(x \/ 10);
    putchar(x % 10 + '0');
}

int n, m, d;
int rt = 1, tot = 1;
ll delta;

struct fireworks {
    int a, b, t;
} F[MAXN];

struct node {
    int son[2], fa;
    ll adx, adk, x, k, dy, lx, rx, rk;
} T[MAXN];

#define son(x, s) T[x].son[s]
#define f(x) T[x].fa

inline void cct(int x, int y, bool loc) { son(x, loc) = y, f(y) = x; }
inline bool get_son(int x) { return son(f(x), 1) == x; }

inline void push_up(int x) {
    if (!x) return;
    T[x].lx = son(x, 0) ? T[son(x, 0)].lx : T[x].x;
    T[x].rx = son(x, 1) ? T[son(x, 1)].rx : T[x].x;
    T[x].rk = son(x, 1) ? T[son(x, 1)].rk : T[x].k;
    T[x].dy = T[son(x, 0)].dy + T[son(x, 1)].dy;
    if (son(x, 1)) T[x].dy += (T[son(x, 1)].lx - T[x].x) * T[x].k;
    if (son(x, 0)) T[x].dy += (T[x].x - T[son(x, 0)].rx) * T[son(x, 0)].rk;
}

inline void addx(int x, ll k) { if (x) T[x].x += k, T[x].adx += k, T[x].lx += k, T[x].rx += k; }
inline void addk(int x, ll k) { if (x) T[x].k += k, T[x].adk += k, T[x].dy += (T[x].rx - T[x].lx) * k, T[x].rk += k; }
inline void push_down(int x) {
    if (T[x].adx) {
        addx(son(x, 0), T[x].adx);
        addx(son(x, 1), T[x].adx);
        T[x].adx = 0;
    }
    if (T[x].adk) {
        addk(son(x, 0), T[x].adk);
        addk(son(x, 1), T[x].adk);
        T[x].adk = 0;
    }
}

inline void rotate(int x) {
    int y = f(x);
    bool loc = get_son(x);
    f(x) = f(y);
    if (f(y)) {
        son(f(y), get_son(y)) = x;
    }
    cct(y, son(x, loc ^ 1), loc);
    cct(x, y, loc ^ 1);
    push_up(y), push_up(x);
}

inline void splay(int x) {
    for (int y = f(x); y; rotate(x), y = f(x))
        if (f(y))
            rotate(get_son(x) == get_son(y) ? y : x);
    rt = x;
}

inline void find() {\/\/找到最高点
    int x = rt, ret;
    while (x) {
        push_down(x);
        if (T[x].k <= 0) ret = x, x = son(x, 0);
        else x = son(x, 1);
    }
    splay(ret);
}

inline void find(ll k) {
    int x = rt, ret;
    while (x) {
        push_down(x);
        if (T[x].x <= k) ret = x, x = son(x, 1);
        else x = son(x, 0);
    }
    splay(ret);
}

int main() {
    n = read(), m = read(), d = read();
    for (int i = 1; i <= m; i++) {
        F[i].a = read(), F[i].b = read(), F[i].t = read();
        delta += F[i].b - F[i].a - (ll) F[i].t * d;
    }

    sort(F + 1, F + m + 1, [](fireworks a, fireworks b) { return a.t < b.t; });

    for (int i = 1; i <= m; i++) {

        find();

        if (T[rt].k) {
            T[++tot] = T[rt], son(tot, 0) = 0;
            T[rt].k = 0;
            cct(tot, son(rt, 1), 1);
            cct(rt, tot, 1);
            push_up(tot), push_up(rt);
        }
        ll D = (ll) d * (F[i].t - F[i - 1].t);
        T[rt].x -= D;
        addx(son(rt, 0), -D);
        addx(son(rt, 1), D);
        push_up(rt);

        find(F[i].a);

        if (T[rt].x < F[i].a) {
            T[++tot] = T[rt], son(tot, 0) = 0;
            T[tot].x = F[i].a, T[rt].k += 1;
            cct(tot, son(rt, 1), 1);
            cct(rt, tot, 1);
            push_up(tot), push_up(rt);
        } else T[rt].k -= 1;
        addk(son(rt, 0), 1);
        addk(son(rt, 1), -1);
        push_up(rt);
    }

    find();
    write(delta + T[son(rt, 0)].dy + (T[rt].x - T[son(rt, 0)].rx) * T[son(rt, 0)].rk);
    return 0;
}