首先我们看到题，发现不会，考虑上网搜题解，然后会发现这是一道dp.
首先这是看出一道dp，先思考(n^2)暴力怎么做，显然我们每个操作必须"连起来"。这样才能确保所有人都被治愈。令 (dp[i]) 表示治疗到 (r[i]) 所需要的最小花费。
我们可以得出 (dp[i] = min_{j = 1}^{m}dp[j] + c[i]), 对于所有 (j) 满足 (r[i] le l[j] + |T[i] - T[j]| + 1), 且 (j ot= i)。这个东西的时间复杂度是 (n^2) 的。
我们发现拆了绝对值之后，每个 (i) 对应的能转移的 (j) 是原序列按 (T) 排序后，对应的一段区间。然后又能发现，这个dp可以想dij一样，每次取最小的更新。
那么我们把它们丢到两棵(对应着拆绝对值)线段树上，然后跑一个很像最短路的东西就行了。
我的写法时间复杂度是 (mlog^2m) , 被wasa855神仙的 (mlogm) 方法爆踩。 说明我太菜了/kk
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 100005
#define pll pair<ll, ll>
int n, m;
struct qus
{
int T, l, r;
ll c;
bool operator < (const qus &o) const
{
return T < o.T;
}
}a[N];
ll dis[N];
priority_queue <pll> q;
bool vis[N], inq[N];
struct Seg
{
set <pll> s[N << 2];
void insert(int rt, int l, int r, int x, pll v)
{
s[rt].insert(v);
if(l == r) return;
int mid = l + r >> 1;
if(x <= mid) insert(rt << 1, l, mid, x, v);
else insert(rt << 1 | 1, mid + 1, r, x, v);
}
void update(int rt, int l, int r, int x, int y, int v, ll p)
{
// cout << l << ' ' << r << ' ' << x << ' ' << y << endl;
if(l == x && r == y)
{
for(; !s[rt].empty() && s[rt].begin()->first <= v;)
{
int u = s[rt].begin()->second;
if(!inq[u])
{
inq[u] = 1;
dis[u] = p + a[u].c;
q.push(make_pair(-dis[u], u));
}
s[rt].erase(s[rt].begin());
}
return;
}
int mid = l + r >> 1;
if(y <= mid) update(rt << 1, l, mid, x, y, v, p);
else if(x > mid) update(rt << 1 | 1, mid + 1, r, x, y, v, p);
else update(rt << 1, l, mid, x, mid, v, p), update(rt << 1 | 1, mid + 1, r, mid + 1, y, v, p);
}
}tr1, tr2;
int main()
{
scanf("%d%d", &n, &m);
for(int i = 1; i <= m; i++)
{
scanf("%d%d%d%d", &a[i].T, &a[i].l, &a[i].r, &a[i].c);
}
sort(a + 1, a + m + 1);
for(int i = 1; i <= m; i++) tr1.insert(1, 1, m, i, make_pair(a[i].l - a[i].T, i));
for(int i = 1; i <= m; i++) tr2.insert(1, 1, m, i, make_pair(a[i].l + a[i].T, i));
for(int i = 1; i <= m; i++) dis[i] = (a[i].l == 1) ? a[i].c : (1ll << 60);
for(int i = 1; i <= m; i++) if(a[i].l == 1) inq[i] = 1, q.push(make_pair(-a[i].c, i));
while(!q.empty())
{
int u = q.top().second; q.pop();
// cout << u << endl;
if(vis[u]) continue;
vis[u] = 1;
if(u != 1) tr1.update(1, 1, m, 1, u - 1, a[u].r - a[u].T + 1, dis[u]);
if(u != m) tr2.update(1, 1, m, u + 1, m, a[u].r + a[u].T + 1, dis[u]);
}
ll ans = (1ll << 60);
for(int i = 1; i <= m; i++)
{
if(a[i].r == n)
{
ans = min(ans, dis[i]);
}
}
if(ans != (1ll << 60)) printf("%lld
", ans);
else printf("-1
");
return 0;
}