求线段树解法

因为这个和扫描线板子很像所以赛时尝试用线段树写，但是比赛中爆零，没想明白怎么写pushup()

感谢各位神仙，悬赏关注

赛时代码WA

#include <stdio.h>
#include <algorithm>
#define N 1000000
#define lc (cur * 2)
#define rc (cur * 2 + 1)
typedef long long ll;
inline ll max(ll x, ll y) {return (x > y) ? x : y;}

struct node{
    int l, r;
    int cnt;
    ll sum;

    int cntl, cntr;
} tree[N*4];

int n, m;
ll f[N];
ll fn[N];

int lenTemp;
ll temp[N*4];

inline void pushup(int cur) {
    if (tree[cur].cnt > 0) {
        tree[cur].cntl = tree[cur].cntr = tree[cur].cnt;
        if (tree[cur].cnt == 1) {
            tree[cur].sum = temp[tree[cur].r] - temp[tree[cur].l] + 1;
        } else {
            tree[cur].sum = 0;
        }
    } else if (tree[cur].l == tree[cur].r) {
        tree[cur].sum = 0;
        tree[cur].cntl = tree[cur].cntr = tree[cur].cnt;
    } else {
        tree[cur].sum = tree[lc].sum + tree[rc].sum;
        if (tree[lc].cntr == 1 && tree[rc].cntl == 1) tree[cur].sum += temp[tree[rc].l] - temp[tree[lc].r] - 1;
        tree[cur].cntl = tree[lc].cntl, tree[cur].cntr = tree[rc].cntr;
    }
}

void init(int cur, int l, int r) {
    tree[cur].l = l, tree[cur].r = r;
    if (l == r) {
        tree[cur].cnt = tree[cur].sum = 0;
        return;
    }
    int mid = (l+r)/2;
    init(lc, l, mid);
    init(rc, mid + 1, r);
    pushup(cur);
}

void work(int cur, int sta) {
    tree[cur].cnt += sta;
    pushup(cur);
}

void update(int cur, int l, int r, int sta) {
    if (tree[cur].l >= l && tree[cur].r <= r) {
        work(cur, sta);
        return;
    }
    int mid = (tree[cur].l + tree[cur].r) / 2;
    if (l <= mid) update(lc, l, r, sta);
    if (r >= mid + 1) update(rc, l, r, sta);
    pushup(cur);
}

void outTree();

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &f[i]);
        fn[i] = f[i] + m - 1;
        temp[++lenTemp] = f[i];
        temp[++lenTemp] = fn[i];
        temp[++lenTemp] = f[i] - 1;
        temp[++lenTemp] = fn[i] + 1;
    }
    std::sort(temp+1, temp+1+lenTemp);
    lenTemp = std::unique(temp+1, temp+1+lenTemp) - temp - 1;
    
    
    for (int i = 1; i <= n; i++) {
        f[i] = std::lower_bound(temp+1, temp+1+lenTemp, f[i]) - temp;
        fn[i] = std::lower_bound(temp+1, temp+1+lenTemp, fn[i]) - temp;
    }
    init(1, 1, lenTemp);
    for (int i = 1; i <= n; i++) {
        update(1, f[i], fn[i], 1);    
        printf("len: %d, i=%d\n", lenTemp, i);
        for (int i = 1; i <= lenTemp; i++) {
            printf("%d ", i);
        }
        printf("\n");
        for (int i = 1; i <= lenTemp; i++) {
            printf("%d ", temp[i]);
        }
        printf("\n");
        printf("[%d, %d]\n", f[i], fn[i]);
        outTree();
    }
    // printf("%d\n", tree[1].sum);
    ll res = 0;
    for (int i = 1; i <= n; i++) {
        update(1, f[i], fn[i], -1);
        res = max(res, tree[1].sum + m);
        update(1, f[i], fn[i], 1);
    }
    printf("%lld", res);
    return 0;
}

void outTree() {
    for (int i = 1; i <= 33; i++) {
        printf("%d: [%d, %d], cnt=%d, sum=%d, cntl=%d, cntr=%d\n", i, tree[i].l, tree[i].r, tree[i].cnt, tree[i].sum, tree[i].cntl, tree[i].cntr);
    }
    printf("\n");
}