题解：NOIP2023 天天爱打卡

• 标签：线段树优化dp
• 先考虑一个朴素的dp, \(f[i]\) 表示前 \(i\) 天, 第 \(i\) 天必打卡能得到的最大能量，有转移：

• \(val(j,i)\) 表示第 \(j\sim i\) 天完成的挑战.

• 乍一看是 \(O(n^2mk)\).

• 优化1： $ \max_{p=1}^{j-2} f[p]$ 可以前缀 \(max\) 优化.

• 优化2：把每个挑战挂在它的终点上，这样每个挑战只会被访问一次.

• 优化3：记 \(g[j] = val(j,i) - d \times (i-j+1) + \max_{p=1}^{j-2} f[p]\), 那么 \(f[i]=\max_{j=i-k+1}^{i} g[j]\)

  这个东西可以用线段树优化，只需要维护区间加，区间求max.

  #include<bits/stdc++.h>
  #define F(i,l,r) for(int i(l);i<=(r);++i)
  #define G(i,r,l) for(int i(r);i>=(l);--i)
  #define int long long
  #define pii pair<int,int>
  using namespace std;
  using ll = long long;
  const int N=2e5+105;
  int c,T,n,m,d,k,cnt=0;
  int x[N],y[N],v[N],g[N],rk[N];
  int mx[N<<2],tag[N<<2];
  vector<pii> e[N];
  inline void pushup(int u){
  	mx[u]=max(mx[u*2],mx[u*2+1]);
  }
  inline void pushdown(int p,int l,int r){
  	if(tag[p]!=0){
  		mx[p*2]+=tag[p];
  		mx[p*2+1]+=tag[p];
  		tag[p*2]+=tag[p];
  		tag[p*2+1]+=tag[p];
  		tag[p]=0;
  	}
  }
  inline void update(int p,int l,int r,int x,int y,int z){
  	if(x>y) return ;
  	if(x<=l && r<=y){
  		tag[p]+=z;
  		mx[p]+=z;
  		return ;
  	}
  	pushdown(p,l,r);
  	int mid=(l+r)>>1;
  	if(x<=mid) update(p*2,l,mid,x,y,z);
  	if(y>mid) update(p*2+1,mid+1,r,x,y,z);
  	pushup(p);
  }
  inline int ask(int p,int l,int r,int x,int y){
  	if(x<=l && r<=y){
  		return mx[p];
  	} pushdown(p,l,r);
  	int mid=(l+r)>>1,maxn=0;
  	if(x<=mid) maxn=max(maxn,ask(p*2,l,mid,x,y));
  	if(y>mid) maxn=max(maxn,ask(p*2+1,mid+1,r,x,y));
  	return maxn;
  }
  inline int get(int x){
  	return lower_bound(rk+1,rk+cnt+1,x)-rk;
  }
  signed main(){
  //	freopen("run.in","r",stdin);
  //	freopen("run.out","w",stdout);
  	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  	cin>>c>>T;
  	while(T--){
  		memset(mx,0,sizeof(mx));
  		memset(tag,0,sizeof(tag));
  		g[0]=0;
  		cnt=0;
  		cin>>n>>m>>k>>d;
  		F(i,1,m) {
  			cin>>x[i]>>y[i]>>v[i];
  			y[i]=x[i]-y[i]+1;
  			rk[++cnt]=x[i];
  			rk[++cnt]=y[i];
  		}
  		sort(rk+1,rk+cnt+1); cnt=unique(rk+1,rk+cnt+1)-rk-1;
  		F(i,1,cnt) e[i].clear(); 
  		F(i,1,m){
  			int xx=get(x[i]),yy=get(y[i]);
  			e[xx].push_back({yy,v[i]});
  		}
  		F(i,1,cnt){
  			if(rk[i]-rk[i-1]>1 || i==1)	update(1,1,cnt,i,i,g[i-1]-d);		
  			else update(1,1,cnt,i,i,g[i-2]-d);		
  			update(1,1,cnt,1,i-1,(rk[i-1]-rk[i])*d);
  //			update(1,1,cnt,i,i,((i==1||rk[i]-rk[i-1]>1)?g[i-1]:g[i-2])-d);
  //			if(i>1) update(1,1,cnt,1,i-1,-(rk[i]-rk[i-1])*d);
  			int siz=e[i].size();
  			F(j,0,siz-1){
  				pii o=e[i][j];
  				update(1,1,cnt,1,o.first,o.second);	
  			}
  			int lx = lower_bound(rk+1,rk+cnt+1,rk[i]-k+1)-rk; 
  			g[i]=max(g[i-1],max(0ll,ask(1,1,cnt,lx,i)));
  		}
  		cout<<g[cnt]<<"\n";
  	}
  	return 0;
  }
  

  总结

• 个人觉得本题的难点应该是要把朴素的dp想对，比如我一开始就没有敢往一维dp上想。

• 再一个就是前两个小优化是不难的，要力求写准确。

• 最后就是离散化之后修改和查询有一些细节很需要注意！