一个感觉很抽象的但是感觉是对的的动态开点

求调

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

#define int long long

using namespace std;
int c,T,n,m,K,d,cnt,maxn,tk,las;
int f[3001][3001],b[200001];

struct Node { int x,y,v; }e[100001];

bool cmp(Node M,Node N) { return M.x^N.x?M.x<N.x:M.y<N.y; }

int tcnt,rt;

struct Tree { int mx,tag1,tag2,l,r; }t[200001<<5];

void nnew(int &x,int l,int r) { t[x=++tcnt]=Tree{0,0,(int)-1e18,0,0}; }

void pushdown(int x,int l,int r) {
    int mid=(l+r>>1);
    if (t[x].tag2!=-1e18) {
        if (!t[x].l) nnew(t[x].l,l,mid);
        t[t[x].l].mx=t[x].tag2,t[t[x].l].tag2=t[x].tag2,t[t[x].l].tag1=0;
        if (!t[x].r) nnew(t[x].r,mid+1,r);
        t[t[x].r].mx=t[x].tag2,t[t[x].r].tag2=t[x].tag2,t[t[x].r].tag1=0;
        t[x].tag2=-1e18;
    }
    if (t[x].tag1) {
        if (!t[x].l) nnew(t[x].l,l,mid);
        t[t[x].l].mx+=t[x].tag1,t[t[x].l].tag1+=t[x].tag1;
        if (!t[x].r) nnew(t[x].r,mid+1,r);
        t[t[x].r].mx+=t[x].tag1,t[t[x].r].tag1+=t[x].tag1;
        t[x].tag1=0;
    }
}

void upd1(int &x,int l,int r,int L,int R,int k) {
    if (!x) nnew(x,l,r);
    if (L>R) return;
    if (L<=l and r<=R) {
        t[x].mx+=k,t[x].tag1+=k;
        return;
    }
    pushdown(x,l,r);
    int mid=(l+r>>1);
    if (L<=mid) upd1(t[x].l,l,mid,L,R,k);
    if (R>mid) upd1(t[x].r,mid+1,r,L,R,k);
    t[x].mx=max(t[t[x].l].mx,t[t[x].r].mx);
}

void upd2(int &x,int l,int r,int L,int R,int k) {
    if (!x) nnew(x,l,r);
    if (L>R) return;
    if (L<=l and r<=R) {
        t[x].mx=k,t[x].tag2=k,t[x].tag1=0;
        return;
    }
    pushdown(x,l,r);
    int mid=(l+r>>1);
    if (L<=mid) upd2(t[x].l,l,mid,L,R,k);
    if (R>mid) upd2(t[x].r,mid+1,r,L,R,k);
    t[x].mx=max(t[t[x].l].mx,t[t[x].r].mx);
}

signed main() {
    scanf("%lld%lld",&c,&T);
    while (T--) {
        scanf("%lld%lld%lld%lld",&n,&m,&K,&d);
        tk=tcnt=rt=0;
        for (int i=1;i<=m;i++) {
            scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].v);
            b[++tk]=e[i].x,b[++tk]=e[i].x-e[i].y+1;
        }
        sort(e+1,e+m+1,cmp);
        sort(b+1,b+tk+1);
        tk=unique(b+1,b+tk+1)-b-1;
        int cnt=1;
        las=maxn=0;
        for (int i=1;i<=tk;i++) {
            upd2(rt,1,n,b[i],b[i],maxn);
            while (e[cnt].x==b[i] and e[cnt].y<=K and cnt<=m) {
                upd1(rt,1,n,e[cnt].x-e[cnt].y+1,n,e[cnt].v-(b[i]-b[i-1])*d);
                ++cnt;
            }
            while (e[cnt].x==b[i] and cnt<=m) ++cnt;
            maxn=max(maxn,t[rt].mx);
        }
        printf("%lld\n",maxn);
    }
    return 0;
}