NOIP2023 T4 天天爱打卡 题解 线段树优化 DP 转移

· · 个人记录

题意

题面给了题意转化的提示的。

题解

感觉只有蓝的难度，但是赛时太菜了没调出来。

首先容易想到考虑选哪些点是不好做的，可以换位思考考虑不选哪些点。

容易发现，以所有 l_i-1 和 r_i+1 为分界点，可以构造出每个分出的区间要么全被选，要么全不被选的最优解。

如上图，橙色线段是“有贡献的区间”，然后青色点是我们选的点。容易发现上面的方案转化成下面的必定是更优的，因为贡献没有变化，还减小了代价。而显然每一个不满足“每个分出的区间要么全被选，要么全不被选”的情况都能规约到上述三种。

那么把这些分界点离散化后，设 dp_i 表示钦定第 i 个分界点不被选的最大收益，记第 i 个分界点的坐标是 p_i。

考虑两种转移，第一种是 [p_{i-1},p_i] 全不被选，此时 dp_i=dp_{i-1}。

然后是考虑 [p_j+1,p_i-1] 全被选的收益。转移大概长这样：

dp_{i}=\max_{j<i}^{p_i-p_j-1\le k}\begin{Bmatrix}dp_{j}-d\times(p_i-p_j-1)+w(i,j)\end{Bmatrix}

其中 w(i,j) 为被 [p_j+1,p_i-1] 完全覆盖的区间的权值和。

然后容易发现 w(i,j) 相当于是一个固定右端点，查询左端点的东西，可以考虑把所有区间 [l_i,r_i] 存在 r_i+1 位置上，然后维护每个区间会影响哪些左端点。具体来说，一个区间 [l_i,r_i] 会对 j\in [0,l_i-1],i'\ge i 的所有 w(i',j) 产生贡献，这个可以直接开一个区间加区间查询最大值的线段树动态维护。

那么式子可以化成：

dp_{i}=-d\times(p_i-1)+\max_{j<i}^{p_i-p_j-1\le k}\begin{Bmatrix}dp_{j}+d\times p_j+w(i,j)\end{Bmatrix}

线段树维护大括号里面的那坨东西，然后双指针维护最左的合法的 j，就做完了，复杂度 O(n\log n)。

貌似写成动态开点线段树会被卡常。

#include<bits/stdc++.h>
#define mem(a,b) memset(a,b,sizeof(a))
#define forup(i,s,e) for(i64 i=(s);i<=(e);++i)
#define fordown(i,s,e) for(i64 i=(s);i>=(e);--i)
using namespace std;
using i64=long long;
#define gc getchar()
i64 read(){
    i64 x=0,f=1;char c;
    while(!isdigit(c=gc))if(c=='-')f=-1;
    while(isdigit(c)){x=x*10+(c-48);c=gc;}
    return f*x;
}
const i64 N=2e5+5,inf=1e18;
i64 c,t,n,m,k,d,sz;//大部分变量和题面相同，sz 是离散化后数的个数
i64 dp[N];
struct query{
    i64 l,v;
};
vector<query> qu[N];//离散化后，存储以 p[i]-1 为右端点的所有区间
struct Node{
    i64 l,r,v;
};
vector<Node> vec;//存储所有区间
struct SegTree{//线段树
    #define mid ((l+r)>>1)
    #define lson l,mid,id<<1
    #define rson mid+1,r,id<<1|1
    i64 querymax[N<<2],mark[N<<2];
    void PushUp(i64 id){
        querymax[id]=max(querymax[id<<1],querymax[id<<1|1]);
    }
    void PushDown(i64 id){
        mark[id<<1]+=mark[id];
        mark[id<<1|1]+=mark[id];
        querymax[id<<1]+=mark[id];
        querymax[id<<1|1]+=mark[id];
        mark[id]=0;
    }
    void Build(i64 l=0,i64 r=sz,i64 id=1){
        mark[id]=0;//记得清空懒标记
        if(l==r){
            querymax[id]=0;
            return;
        }
        Build(lson);Build(rson);
        PushUp(id);
    }
    void Update(i64 L,i64 R,i64 X,i64 l=0,i64 r=sz,i64 id=1){
        if(L<=l&&r<=R){
            querymax[id]+=X;
            mark[id]+=X;
            return;
        }
        if(mark[id]) PushDown(id);
        if(L<=mid) Update(L,R,X,lson);
        if(mid< R) Update(L,R,X,rson);
        PushUp(id);
    }
    i64 Query(i64 L,i64 R,i64 l=0,i64 r=sz,i64 id=1){
        if(L<=l&&r<=R){
            return querymax[id];
        }
        if(mark[id]) PushDown(id);
        i64 res=-inf;
        if(L<=mid) res=max(res,Query(L,R,lson));
        if(mid< R) res=max(res,Query(L,R,rson));
        return res;
    }
}mt;
void solve(){
    n=read();m=read();k=read();d=read();
    vec.clear();
    vector<i64> lsh;
    forup(i,1,m){
        i64 x=read(),y=read(),v=read();
        i64 l=x-y+1,r=x;
        lsh.push_back(l-1);lsh.push_back(r+1);
        vec.push_back(Node{l,r,v});
    }
    sort(lsh.begin(),lsh.end());
    lsh.erase(unique(lsh.begin(),lsh.end()),lsh.end());
    sz=lsh.size();
    forup(i,0,sz-1){
        dp[i]=0;
        qu[i].clear();
    }
    mt.Build();//多测记得清空
    for(auto i:vec){
        i64 l=lower_bound(lsh.begin(),lsh.end(),i.l-1)-lsh.begin(),r=lower_bound(lsh.begin(),lsh.end(),i.r+1)-lsh.begin(),v=i.v;
        qu[r].push_back(query{l,v});//离散化后存到右端点上
    }
    i64 pl=0;
    mt.Update(0,0,lsh[0]*d);//第一个分界点的答案肯定是 0，直接上传
    forup(i,1,sz-1){
        dp[i]=dp[i-1];
        for(auto j:qu[i]) mt.Update(0,j.l,j.v);//维护 w(i,j)
        while(lsh[i]-lsh[pl]-1>k) ++pl;//双指针维护合法的转移
        if(pl<i) dp[i]=max(dp[i],mt.Query(pl,i-1)-(lsh[i]-1)*d);//注意可能不存在合法的转移，会死循环
        mt.Update(i,i,dp[i]+lsh[i]*d);
    }
    printf("%lld\n",dp[sz-1]);
}
signed main(){
    c=read();t=read();
    while(t--){
        solve();
    }
}