题目描述

一张纸带，被划分成很多长度为 $1$ 的网格，现在有 $N$ 张贴纸，第 $i$ 张可以覆盖 $a_i$ 到 $b_i$ 范围内的格子，代价为 $c_i$。现在要用这些贴纸覆盖 $[L,R]$ 的所有格子，需要最小化总代价。数据保证 $\forall i,L\leq a_i\leq b_i\leq R$。

解法

有代价的线段覆盖模板题。这类题目解法很多，本篇题解给出其中三种不同思路，其中重点介绍第三种。

有兴趣的读者可以自行思考其他解法，如 fhqTreap。

算法 1

最短路。

把每一个网格看做有向图的顶点，从每个 $a_i$ 向 $b_i$ 连一条边权为 $c_i$ 的边。

然后从每个点向前一个点连一条边权为 $0$ 的边。

接下来的操作就很简单了——跑最短路板子即可。

这种算法实现相对较为简单，且思维难度不高。复杂度同最短路板子。

下面两种解法均基于对 DP 的优化。

算法 2

不难想到一种 $O(N^2)$ 的 DP 解法（纸带已按照右端点升序排序）：
$$ f_i=min\{f_j\}+c_i,a_i-1\leq b_j $$
下面考虑进行优化。我们可以用一棵线段树动态维护 $f_j$ 部分，并动态查询区间最小值。区间左端点可以二分得到。

蓝书和其他几篇题解采用的思路与这种解法较为相似，且已作出详细讲解，因此这里只做简单介绍，不展开讨论。

下面一种算法采用改进 DP 的另一种可行思路。

算法 3

虽然线段树拥有优秀的复杂度，但其也有常数较大、调试难度高等缺点。我们能否使用其他数据结构代替？

不难发现每次进行修改操作都相当于在末尾添加一个元素，需要执行的操作只有在已经添加的元素中查询区间最值。

这里提供一种思路：使用经过改进的 ST 表进行优化。

实际应用 ST 表时，我们习惯用 $st_{i,j}$ 表示区间 $[i,i+2^j-1]$ 内的最值。现在将其反过来，用 $st_{i,j}$ 表示 $[i-2^j+1,i]$ 内的最值。

不难发现，这样一来就可以用一枚 $\log$ 的时间在 ST 表末尾插入元素，询问区间最值的复杂度为 $O(1)$。我们还可以用 $O(1)$ 的时间删除末尾元素——虽然该操作在本题中没有用到。

这样的 ST 表已经可以满足求解本题的需要了。

算法 2、3 的时间复杂度均为 $O(N\log N)$。

#include<cstdio>
#include<algorithm>
using namespace std;
const long long INF=1145141919810931;
int n,m,e;
long long f[10086],ans=INF;
long long Min(long long a,long long b){return a<b?a:b;}
struct asdf{
    int a,b,c;
    bool operator <(const asdf &z)const{return b!=z.b?b<z.b:a<z.a;}
}cow[10086];
struct stlist{
    long long mn[10086][15];int cnt,lg[10086];
    bool clear(){cnt=0;return true;}
    bool push(long long x){
        cnt++;lg[cnt]=lg[cnt-1]+((1<<lg[cnt-1])==cnt);
        mn[cnt][0]=x;
        for(int i=1;i<lg[cnt];i++)
            mn[cnt][i]=Min(mn[cnt][i-1],mn[cnt-(1<<(i-1))][i-1]);
        return true;
    }
    long long query(int l,int r){
        if(l==r)return mn[r][0];
        int lo=lg[r-l+1]-1;
        return Min(mn[r][lo],mn[l+(1<<lo)-1][lo]);
    }
}st;
int read(){
    char ch=getchar();int nn=0,ssss=1;
    while(ch<'0'||ch>'9'){if(ch=='-')ssss*=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){nn=nn*10+(ch-'0');ch=getchar();}
    return nn*ssss;
}
int binget(int pos){//二分区间左端点,写二分太麻烦了所以这里用倍增代替
    int np=pos-1;
    for(int i=st.lg[pos-1]-1;i>=0;i--)
        if(np-(1<<i)>0&&cow[np-(1<<i)].b>=cow[pos].a-1)np-=(1<<i);
    return np;
}
int main(){
    n=read();m=read();e=read();
    for(int i=1;i<=n;i++){
        cow[i].a=read();cow[i].b=read();cow[i].c=read();
    }
    sort(cow+1,cow+n+1);
    for(int i=1;i<=n;i++){
        f[i]=cow[i].c;
        if(cow[i].a==m){
            if(cow[i].b==e)ans=Min(ans,f[i]);
            st.push(f[i]);
            continue;
        }
        if(cow[i-1].b<cow[i].a-1){//这个蛮重要的,不理解的话可以从darkbzoj下载数据找n=20那组看看
            st.push(INF);
            continue;
        }   
        int lft=binget(i);
        f[i]+=st.query(lft,i-1);
        st.push(f[i]);
        if(cow[i].b==e)ans=Min(ans,f[i]);
    }
    if(ans!=INF)printf("%lld",ans);
    else printf("-1");
}