Loj 3282 治疗计划

Posted on | Views:

Dijkstra + 线段树.

两个方案 $[l_i,r_i],[l_j,r_j]​$ 执行后能合并成一个健康区间的条件为 $R_i-L_j+1\ge |T_i-T_j|​$ ,最后要合并成 $[1,n]​$ .
可以看成从所有 $L_i=1$ 的区间出发,若区间 $i,j$ 能合并,则有边 $i\to j$ ,边权为 $C_j$ ,求到 $R_i=n$ 的区间的最短路.

考虑 $i$ 能向哪些 $j$ 连边,若 $T_j\le T_i$ ,则需要满足 $R_i-T_i+1\ge L_j-T_j$ ,否则需要满足 $R_i+T_i+1\ge L_j+T_j$ .
开两棵线段树,都以 $T$ 为下标,在 Dijkstra 过程中需要找 $i​$ 的所有出边,在两棵线段树上分别找即可.

每个点的入边的边权是相同的,所以每个 $j$ 只会被 $dis$ 最小的 $i$ 更新,之后可以将其删去,时间复杂度 $O(n\log n)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(ll x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(ll x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int N = 1e5 + 10, inf = 0x7fffffff;
int n, m;
struct info
{
	int t, l, r, c;
	bool operator < (const info &rhs) const
	{
		return t < rhs.t;
	}
} p[N];
vector<int> E;
struct Segtree
{
	int mi[N << 2];
	void pushup(int x)
	{
		mi[x] = min(mi[x << 1], mi[x << 1 | 1]);
	}
	void BuildTree(int x, int l, int r, int sgn)
	{
		if (l == r)
		{
			mi[x] = p[l].l + p[l].t * sgn;
			return;
		}
		int mid = (l + r) >> 1;
		BuildTree(x << 1, l, mid, sgn);
		BuildTree(x << 1 | 1, mid + 1, r, sgn);
		pushup(x);
	}
	void erase(int x, int l, int r, int pos)
	{
		if (l == r)
		{
			mi[x] = inf;
			return;
		}
		int mid = (l + r) >> 1;
		if (pos <= mid)
			erase(x << 1, l, mid, pos);
		else
			erase(x << 1 | 1, mid + 1, r, pos);
		pushup(x);
	}
	void query(int x, int l, int r, int L, int R, int bound)
	{
		if (mi[x] > bound)
			return;
		if (l == r)
		{
			E.push_back(l);
			return;	
		}	
		int mid = (l + r) >> 1;
		if (L <= mid)
			query(x << 1, l, mid, L, R, bound);
		if (R > mid)
			query(x << 1 | 1, mid + 1, r, L, R, bound);
	}
} T1, T2;
ll dis[N];
priority_queue<pair<ll, int> > q;
ll Dijkstra()
{
	for (int i = 1; i <= m; ++i)
		if (p[i].l == 1)
		{
			dis[i] = p[i].c;
			q.push(make_pair(-dis[i], i));
			T1.erase(1, 1, m, i);
			T2.erase(1, 1, m, i);
		}
	while (!q.empty())
	{
		int u = (q.top()).second;
		q.pop();
		if (p[u].r == n)
			return dis[u];
		E.clear();
		if (u > 1)
			T1.query(1, 1, m, 1, u - 1, p[u].r - p[u].t + 1);
		if (u < m)
			T2.query(1, 1, m, u + 1, m, p[u].r + p[u].t + 1);
		for (int v : E)
		{
			dis[v] = dis[u] + p[v].c, q.push(make_pair(-dis[v], v));
			T1.erase(1, 1, m, v);
			T2.erase(1, 1, m, v);
		}
	}
	return -1;
}
int main()
{
	n = read(), m = read();
	for (int i = 1; i <= m; ++i)
	{
		p[i].t = read();
		p[i].l = read(), p[i].r = read();
		p[i].c = read();
	}
	sort(p + 1, p + 1 + m);
	T1.BuildTree(1, 1, m, -1);
	T2.BuildTree(1, 1, m, 1);
	cout << Dijkstra() << '\n';
	return 0;
}