求助NOIP T4卡常

跑的超级慢，本地大样例8s，洛谷评测机56pts

#include<bits/stdc++.h>
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
using namespace std;
const ll N=1000010,INF=1e9+7,INFF=0x3f3f3f3f3f3f3f3f;
inline ll max(ll x,ll y){return x>y?x:y;}
inline ll min(ll x,ll y){return x<y?x:y;}
inline void swap(ll &x,ll &y){x^=y^=x^=y;}
ll c,t,n,m,k,d,tot,ans,cnt;
vector<ll> s;
vector<pair<ll,ll> > h[N];
unordered_map<ll,ll> ls,rs;
inline ll read(){
    char c=getchar();ll x=0,f=1;
    while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}
    while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
struct SegmentTree{
    ll l,r;
    ll dat,tag;
    #define l(x) tree[x].l
    #define r(x) tree[x].r
    #define dat(x) tree[x].dat
    #define tag(x) tree[x].tag
}tree[N<<3];
void pushup(ll p){
    dat(p)=max(dat(l(p)),dat(r(p)));
}
ll build(){
    ll p=++cnt;
    l(p)=r(p)=0;
    dat(p)=tag(p)=0;
    return p;
}
void pushdown(ll p){
    if(!tag(p))return;
    if(l(p))dat(l(p))+=tag(p),tag(l(p))+=tag(p);
    if(r(p))dat(r(p))+=tag(p),tag(r(p))+=tag(p);
    tag(p)=0;
}
void insert(ll p,ll l,ll r,ll pos,ll val){
    if(l==r){dat(p)+=val;return;}
    ll mid=(l+r)>>1;
    pushdown(p);
    if(pos<=mid){
        if(!l(p))l(p)=build();
        insert(l(p),l,mid,pos,val);
    }
    else{
        if(!r(p))r(p)=build();
        insert(r(p),mid+1,r,pos,val);
    }
    pushup(p);
}
void change(ll p,ll l,ll r,ll L,ll R,ll val){
    if(L>R)return;
    if(L<=l&&r<=R){
        dat(p)+=val;tag(p)+=val;
        return;
    }
    ll mid=(l+r)>>1;
    pushdown(p);
    if(L<=mid&&l(p))change(l(p),l,mid,L,R,val);
    if(R>mid&&r(p))change(r(p),mid+1,r,L,R,val);
    pushup(p);
}
ll query(ll p,ll l,ll r,ll L,ll R){
    if(L>R)return -INFF;
    if(L<=l&&r<=R)return dat(p);
    ll mid=(l+r)>>1,val=-INFF;
    pushdown(p);
    if(L<=mid&&l(p))val=max(val,query(l(p),l,mid,L,R));
    if(R>mid&&r(p))val=max(val,query(r(p),mid+1,r,L,R));
    return val;
}
void add(int x){
    if(x<=0)return;
    if(!rs[x])rs[x]=++tot,s.push_back(x);
}
int main(){
    c=read();t=read();
    while(t--){
        ans=cnt=tot=0;dat(0)=-INFF;
        s.clear();ls.clear();rs.clear();
        n=read();m=read();k=read();d=read();
        for(ll i=1;i<=m;i++){
            ll x=read(),y=read(),v=read();
            if(y<=k){
                ls[x-y+1]=1;
                add(x-1);add(x);add(x+1);
                add(x-y);add(x-y+1);add(x-y+2);
                h[rs[x]].push_back(make_pair(x-y+1,v));
            }
        }
        build();
        insert(1,0,n,0,-d*n);
        sort(s.begin(),s.end());
        for(ll i=0;i<(ll)s.size();i++){
            ll r=s[i],lst=ans;
            insert(1,0,n,r,-d*(n-r));
            for(pair<ll,ll> z:h[rs[r]])
                change(1,0,n,0,z.fi-1,z.se);
            ans=max(ans,query(1,0,n,max(0,r-k),r-1)+d*(n-r));
            insert(1,0,n,r,ls[r+1]?lst:ans);
        }
        printf("%lld\n",ans);
        for(int i=1;i<=tot;i++)h[i].clear();
    }
    return 0;
}