AcWing 296. 清理班次2 线段树优化dp

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=1e5,M=90000;
const ll INF=1e15;
int n,m,e;
struct node{
	int l,r,w;
	bool operator< (const node &t) const 
	{
		return r<t.r;
	} 
}range[N];
struct Node{
	int l,r;
	ll v;
}tr[M*4];
void pushup(int u)
{
	tr[u].v=min(tr[u<<1].v,tr[u<<1|1].v);
}
void build(int u,int l,int r)
{
	tr[u]={l,r,INF};
	if(l==r)
		return ;
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
} 
void update(int u,int k,ll v)
{
	if(tr[u].l==tr[u].r)
	{
		tr[u].v=min(tr[u].v,v);
		return ;
	}
	int mid=tr[u].l+tr[u].r>>1;
	if(k<=mid)
		update(u<<1,k,v);
	else
		update(u<<1|1,k,v);
	pushup(u); 
}
ll query(int u, int l, int r)
{
    if (tr[u].l>=l&&tr[u].r<=r) 
		return tr[u].v;

    int mid=tr[u].l+tr[u].r>>1;
    ll res=INF;
    if(l<=mid) 
		res=query(u<<1,l,r);
    if(r>mid) 
		res=min(res,query(u<<1|1,l,r));
    return res;
}
int main()
{
    scanf("%d%d%d",&n,&m,&e);
    //只需要覆盖这个区间
	//所以线段树也只建这个区间 
    build(1,m-1,e);
    update(1,m-1,0);
    for (int i=0;i<n;i++)
    {
        int l,r,w;
        scanf("%d%d%d",&l,&r,&w);
        range[i]={l,r,w};
    }
    sort(range,range+n);
    for (int i=0;i<n;i++)
    {
        int l=range[i].l,r=range[i].r,w=range[i].w;
        ll v=query(1,l-1,r-1)+w;  // f[r]
        update(1,r,v);
    }
    ll res=query(1,e,e);
    if (res==INF)
		res=-1;
    printf("%lld\n", res);

    return 0;
}

AcWing 296. 清理班次2 线段树优化dp

原文：https://www.cnblogs.com/QingyuYYYYY/p/12595346.html