LOJ3282. 「JOISC 2020 Day4」治疗计划

考虑一个 $dp$ ,设 $dp[R][t]$ 表示在 $t$ 时刻已经解决了 $1 \sim R$ 的所有患者。考虑转移就是枚举下一个治疗计划用哪一个。设下一个治疗计划为 $(l,r,c)$ 那么分为两类:

  • $c > t$ ,那么在下一次使用治疗计划的时间在现在之后,由于中间不能有剩余的患者,有 $l \le R-(c-t)$ ,也就是 $c > t,l + c \le R+t$ 。
  • $c < t$ ,也就是说之前进行了一次治疗计划用来覆盖 $R$ 后的一段,那么中间没有剩余患者的条件是 $l \le R - (t-c)$ ,也就是 $l - c \le R - t$ 。

在这两种情况下,可以转移到 $dp[r][c]$ 。

当然,也可以画一个图来形象的理解:

image.png

其中三个段分别是三个治疗计划,中间的斜线是由于患者在进行感染,后面的人时刻会往前感染。

然后不难发现这两个条件是可以分别计算的,因此只讨论其中第一个条件。不难发现这个 $dp$ 就是一个从点向二维矩形内所有点连边,然后求最短路的问题。可以直接套用弹跳的解法。如果直接这么写了交上去,很可能会获得一个 39 分,后面的点基本都 T 了。

但是事实上,由于是一个前缀,可以把线段树上每个点开 $\text{set}$ 变成线段树上只有叶子开 $\text{set}$ ,因为比较和弹出都只会拿集合中的最小值,所以非叶点就维护一个区间最小值即可,于是就可以 $O(n\log^2 n) \to 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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"

using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int sz;

struct fk {
int t , T , l , r , c;
} A[MAXN] ;

multiset<pii> S[MAXN << 2][2];

void ins( int rt , int l , int r , int idx ) {
S[rt][0].insert( mp( A[idx].l + A[idx].T - 1 , idx ) );
S[rt][1].insert( mp( A[idx].l - A[idx].T - 1 , idx ) );
if( l == r ) return;
int m = l + r >> 1;
if( A[idx].t <= m ) ins( rt << 1 , l , m , idx );
else ins( rt << 1 | 1 , m + 1 , r , idx );
}

priority_queue<pair<ll,int>> Q;
ll dis[MAXN];
int vis[MAXN];

ll ds;

void era( int rt , int w , pair<int,int> p ) {
while( rt ) {
S[rt][w].erase( S[rt][w].find( p ) );
rt >>= 1;
}
}
int w , lim , L , R;
void fuck( int rt , int l , int r ) {
if( S[rt][w].empty() ) return;
int i = S[rt][w].begin() -> se;
if( lim < ( w ? A[i].l - A[i].T - 1 : A[i].l + A[i].T - 1 ) ) return;
if( l == r ) {
while( lim >= ( w ? A[i].l - A[i].T - 1 : A[i].l + A[i].T - 1 ) ) {
if( !vis[i] && dis[i] > ds ) {
dis[i] = ds;
vis[i] = 1;
Q.push( mp( -( ds + A[i].c ) , i ) );
}
era( rt , w , *S[rt][w].begin() );
if( S[rt][w].empty() ) return;
i = S[rt][w].begin() -> se;
}
return;
}
int m = l + r >> 1;
if( L <= m ) fuck( rt << 1 , l , m );
if( R > m ) fuck( rt << 1 | 1 , m + 1 , r );
}

void solve() {
cin >> n >> m;
vi ts;
rep( i , 1 , m ) {
int t , l , r , c;
scanf("%d%d%d%d",&t,&l,&r,&c);
A[i] = (fk) { 0 , t , l , r , c };
ts.pb( t );
}
sort( all( ts ) );
ts.erase( unique( all( ts ) ) , ts.end() );
rep( i , 1 , m ) A[i].t = lower_bound( all( ts ) , A[i].T ) - ts.begin() + 1;
sz = ts.size();
rep( i , 1 , m ) if( A[i].l != 1 ) ins( 1 , 1 , sz , i );
// cout << "OK" << endl;
memset( dis , 0x3f , sizeof dis );
rep( i , 1 , m )
if( A[i].l == 1 ) dis[i] = 0 , Q.push( mp( -A[i].c , i ) );
while( !Q.empty() ) {
auto t = Q.top().se; ds = -Q.top().fi; Q.pop();

w = 0 , lim = A[t].r + A[t].T , L = A[t].t , R = sz;
fuck( 1 , 1 , sz );
w = 1 , lim = A[t].r - A[t].T , L = 1 , R = A[t].t - 1 ;
if( A[t].t ) fuck( 1 , 1 , sz );
}
ll as = 0x3f3f3f3f3f3f3f3f;
rep( i , 1 , m ) if( A[i].r == n ) as = min( as , dis[i] + A[i].c );
cout << ( as > 1e18 ? -1 : as ) << endl;
}

signed main() {
// freopen("04-22.in","r",stdin);
// int T;cin >> T;while( T-- ) solve();
solve();
}
文章作者: yijan
文章链接: https://yijan.co/2021/04/19/loj3282-joisc-2020-day4-zhi-liao-ji-hua/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog