1. Description
小 T 同学非常热衷于跑步。为了让跑步更加有趣，他决定制作一款叫做《天天爱打卡》的软件，使得用户每天都可以进行跑步打卡。
开发完成后，小 T 同学计划进行试运行，他找了大 Y 同学来帮忙。试运行共 \(n\) 天，编号为从 \(1\) 到 \(n\)。
对大 Y 同学来说，如果某天他选择跑步打卡，那么他的能量值会减少 \(d\)。初始时，他的能量值是 \(0\)，并且试运行期间他的能量值可以是负数。
而且大 Y 不会连续跑步打卡超过 \(k\) 天；即不能存在 \(1\le x\le n-k\)，使得他在第 \(x\) 到第 \(x+k\) 天均进行了跑步打卡。
小 T 同学在软件中设计了 \(m\) 个挑战，第 \(i\)（\(1\le i \le m\)）个挑战可以用三个正整数 \((x_i,y_i,v_i)\) 描述，表示如果在第 \(x_i\) 天时，用户已经连续跑步打卡至少 \(y_i\) 天（即第 \(x_i-y_i+1\) 到第 \(x_i\) 天均完成了跑步打卡），那么小 T 同学就会请用户吃饭，从而使用户的能量值提高 \(v_i\)。
现在大 Y 想知道，在软件试运行的 \(n\) 天结束后，他的能量值最高可以达到多少？
2. Solution
这道题正解使用线段树优化 DP，比较简单，这里按下不表，讲一下我在打模拟赛时的思路（事实上没有写代码）。
首先一拿到这道题，我们不难写出一个很暴力的 DP 状态和转移，令 \(f_{i,j}\) 表示在第 \(i\) 天时已经连续打卡 \(j\) 天可得到的最大能量值，转移显然可以分为两步进行：
第一步，不考虑在第 \(i\) 天可以提交的任务，\(f_{i,j}=f_{i-1,j-1}\)，特别的，\(f_{i,0}=\max_{j=0}^k(f_{i-1,j})\)。
第二步，通过对应的连续打卡天数来领取奖励，具体的，每一个在第 \(i\) 天可以提交的任务可以写成 \((y,v)\) 的形式，表示对于 \(f_{i,j}\leftarrow f_{i,j}+v\ (j\ge y)\)。
时间复杂度应该不难做到 \(O(nk)\) 从而拿到 \(36\) 分，这里放一点核心的代码：
for(int i=1;i<=m;i++)add[a[i].x][a[i].y]+=a[i].v;
for(int j=0;j<=k;j++)f[0][j]=-j*d;
for(int i=1;i<=n;i++){for(int j=1;j<=k;j++)f[i][j]=f[i-1][j-1]-d;for(int j=0;j<=k;j++)tomax(f[i][0],f[i-1][j]); for(int j=1;j<=k;j++){add[i][j]+=add[i][j-1];f[i][j]+=add[i][j];}
}
最后的答案就是 \(\max_{j=0}^k f_{n,j}\)
现在考虑怎么优化这个过程。会发现，转移实际上可以被细分为三步，不妨将 \(f_{i+1,j}\) 记为 \(f^\prime_j\)，将 \(f_{i,j}\) 记为 \(f_{j}\)。
- 将 \(f^\prime_{0}\) 设置为 \(f\) 的全局最大值。
- 将 \(f\) 下标位于 \([0,k-1]\) 的部分整体减去 \(d\)，并且复制到 \(f^\prime\) 下标为 \([1,k]\) 的位置。
- 根据可提交的任务进行区间加。
这个东西很容易通过线段树做到 \(O(n\log n)\)，具体实现时可以通过一个变量记录当前实际下标为 \(0\) 的位置而非直接平移数组。
#define pii pair<int,int>
int now;
vector<pii>modify[N];
struct Segment_tree{int num;int mx[N<<2],tag[N<<2];#define ls p<<1#define rs p<<1|1#define mid (l+r>>1)void pushup(int p){mx[p]=max(mx[ls],mx[rs]);}void Tag(int p,int v){tag[p]+=v;mx[p]+=v;}void pushdown(int p){Tag(ls,tag[p]);Tag(rs,tag[p]);tag[p]=0;}void build(int p,int l,int r){mx[p]=-inf,tag[p]=0;if(l==r)return ;build(ls,l,mid),build(rs,mid+1,r);}void change(int p,int l,int r,int x,int v){if(l==r){mx[p]=v;return ;}pushdown(p);if(mid>=x)change(ls,l,mid,x,v);else change(rs,mid+1,r,x,v);pushup(p);}void change(int p,int l,int r,int L,int R,int v){if(L<=l&&r<=R)return Tag(p,v);pushdown(p);if(mid>=L)change(ls,l,mid,L,R,v);if(mid<R)change(rs,mid+1,r,L,R,v);pushup(p);}int query(int p,int l,int r,int x){if(l==r)return mx[p];pushdown(p);if(mid>=x)return query(ls,l,mid,x);return query(rs,mid+1,r,x);}void change(int l,int r,int v){if(l<=r)change(1,0,k,l,r,v);else{change(1,0,k,l,k,v);change(1,0,k,0,r,v);}}void change(int x,int v){change(1,0,k,x,v);}#undef ls#undef rs#undef mid
}Set;
void solve(){for(int i=1;i<=n;i++)modify[i].clear();for(int i=1;i<=m;i++){if(a[i].y>k)continue;modify[a[i].x].push_back({a[i].y,a[i].v});}Set.build(1,0,k);now=0;Set.change(1,0,k,0,0);for(int i=1,val0;i<=n;i++){val0=Set.mx[1];Set.change(now,(now+k-1)%(k+1),-d);now--;if(now==-1)now=k;Set.change(now,val0); for(auto tmp:modify[i])Set.change((now+tmp.first)%(k+1),(now+k)%(k+1),tmp.second); }write(Set.mx[1]),Nxt;
}
#undef pii
但是这个时间复杂度仍然无法直接通过这道题，所以我们仍然需要进一步考虑优化。
发现第三步操作的时间复杂度单次只为 \(O(\log n)\)，而操作一共只有 \(m\) 次，所以时间复杂度尚可接受，我们需要优化的实际上只有第一步，第二步。而这两步实际上是比较简单的操作，我们可以尝试快速转移掉一连串没有第三步操作的位置 \(i\) 来保证时间复杂度的正确。
我们不妨假定原来的 dp 数组仍然为 \(f\)，转移一次之后的数组为 \(f^\prime\)。
设 \(mx=\max_{j=0}^k f_j\)，那么根据上面的转移不难得到：\(f^\prime=\{mx,f_0-d,f_1-d\dots f_{k-1}-d\}\)。
因为 \(d\ge 0\)，所以 \(\max_{i=0}^{k-1}(f_{i}-d)\le \max_{i=0}^{k} (f_i)-d\le mx\)，那么再转移一次后得到的数组就是：\(f^{\prime\prime}=\{mx,mx-d,f_0-2d\dots f_{k-2}-2d\}\)。
以此类推，我们发现连续转移 \(x\) 次后，dp 数组应该是：
- \(x\ge k+1,\{mx,mx-d\dots mx-kd\}\)。
- \(x<k+1,\{mx,mx-d\dots mx-(x-1)d,f_0-xd\dots f_{k-x}-xd\}\)
不难发现整个 dp 数组实际上由一个首项为 \(mx\)，公差为 \(d\) 的等差数列和原数组的一部分减去若干个 \(d\) 拼接得到的。
但是如果仍然使用线段树的话，我们不太好去进行这个操作，所以……
来和我写一辈子平衡树吧！我什么都会做的。
是的，我们可以通过平衡树来维护这个过程，实现是比较简单的，主要的难点在区间操作时，一个节点维护的等差数列可能有部分是要增加的，有部分是不用的，但是这样的节点只会有一个，此时将平衡树分裂成三份，从而将这个节点独立出来，之后再将这个节点分裂成两个即可，具体实现时可以在寻找这个节点的过程中同时分裂平衡树。
时间复杂度和平衡树中的节点数有关，而每一个操作最多只会增加三个节点（操作 \(1\) 一个，操作 \(2\) 一个，操作 \(3\) 一个），稍微重复利用一下节点，每个操作就最多只会增加两个节点，时间复杂度即为 \(O(tm\log m)\)，显然应该通过。
3. Code
const int N=1e5+5,M=2e5+5;
const ll inf=0x3F3F3F3F3F3F3F3F;
mt19937 ran;
int n,m,k,d,rt;
struct Modify{int x,y,v;bool operator <(const Modify &T)const{return x<T.x;}
}a[N];
struct Node{int len;ll x,k;Node(int _len=0,ll _x=-inf,ll _k=0){len=_len,x=_x,k=_k;}Node operator +=(const ll &T){x+=T;return *this;}
};
//----平衡树
#define Siz(x) (x==0?0:siz[x])
#define Cnt(x) (x==0?0:cnt[x])
int num;
Node val[M];
int ch[M][2],siz[M],cnt[M];
ll mx[M],tag[M];
unsigned int c[M];
int New(Node _v=Node(),int _p=-1){int p=(~_p)?_p:++num;val[p]=_v;ch[p][0]=ch[p][1]=0,siz[p]=1,cnt[p]=_v.len,mx[p]=_v.x,tag[p]=0;c[p]=ran();return p;
}
void pushup(int p){siz[p]=1,cnt[p]=val[p].len,mx[p]=val[p].x;if(ch[p][0]){siz[p]+=siz[ch[p][0]];cnt[p]+=cnt[ch[p][0]];tomax(mx[p],mx[ch[p][0]]);}if(ch[p][1]){siz[p]+=siz[ch[p][1]];cnt[p]+=cnt[ch[p][1]];tomax(mx[p],mx[ch[p][1]]);}
}
void Tag(int p,ll v){val[p]+=v;tag[p]+=v;mx[p]+=v;
}
void pushdown(int p){if(ch[p][0])Tag(ch[p][0],tag[p]);if(ch[p][1])Tag(ch[p][1],tag[p]);tag[p]=0;
}
int merge(int x,int y){if(x==0&&y==0)return 0;if(x==0)return y;if(y==0)return x;if(c[x]<c[y]){pushdown(x);ch[x][1]=merge(ch[x][1],y);pushup(x);return x;}else{pushdown(y);ch[y][0]=merge(x,ch[y][0]);pushup(y);return y;}
}
pii split(int p,int sz){if(!p)return {0,0};pushdown(p);if(sz<=Siz(ch[p][0])){pii tmp=split(ch[p][0],sz);ch[p][0]=tmp.second;pushup(p); return {tmp.first,p};}else{pii tmp=split(ch[p][1],sz-Siz(ch[p][0])-1);ch[p][1]=tmp.first;pushup(p);return {p,tmp.second};}
}
int pre,mid,suf;
void find(int p,int ct){if(Cnt(ch[p][0])>=ct){find(ch[p][0],ct);ch[p][0]=suf;suf=p;return pushup(p);}ct-=Cnt(ch[p][0]);if(ct<=val[p].len){pre=ch[p][0],mid=p,suf=ch[p][1];ch[p][0]=ch[p][1]=0;return pushup(p);}find(ch[p][1],ct-val[p].len);ch[p][1]=pre;pre=p;return pushup(p);
}
#undef Siz
#undef Cnt
//----平衡树
void init(){num=0;int x=New(Node(1,0,0)),y=New(Node(k,-inf,0));rt=merge(x,y);
}
void trans(int x){//快速完成 x 次操作 1 与操作 2 if(!x)return ;ll x0=mx[rt];if(x>=k+1){num=0;rt=New(Node(k+1,x0,-d));return ;}find(rt,k-x+1);int llen=k-x+1-cnt[pre];Node tmp=Node(llen,val[mid].x,val[mid].k); rt=merge(pre,New(tmp,mid));Tag(rt,-1ll*x*d);rt=merge(New(Node(x,x0,-d)),rt);
}
void modify(int x,int v){//完成一次操作 3 if(x>k)return ;find(rt,x);Node Pre=Node(x-cnt[pre],val[mid].x,val[mid].k);Node Suf=Node(val[mid].len-x+cnt[pre],0ll+val[mid].x+1ll*val[mid].k*(x-cnt[pre]),val[mid].k);rt=merge(pre,New(Pre,mid));int need=suf;if(Suf.len){int idx=New(Suf);need=merge(idx,need);}Tag(need,v);rt=merge(rt,need);
}
signed main(){int type,t;read(type),read(t);while(t--){read(n),read(m),read(k),read(d);for(int i=1;i<=m;i++)read(a[i].x),read(a[i].y),read(a[i].v);sort(a+1,a+m+1);init();for(int i=1,las=0;i<=m;i++){trans(a[i].x-las);las=a[i].x;modify(a[i].y,a[i].v);}write(mx[rt]),Nxt;}
}