【ACDream】1074 风之国 线段树+DP

1
2
3
4
5
6
7
8
9
3 3
63 0 132
2 3
1 3
2 1
3 2
63 0 132
2 3
1 2

1
2
132
63

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
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long Int ;
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define rt l , r , o
#define root 1 , n , 1
#define lson l , m , ls
#define rson m + 1 , r , rs
#define mid ( ( l + r ) >> 1 )
#define clear( A , X ) memset ( A , X , sizeof A )
const int maxN = 100005 ;
const int oo = 0x3f3f3f3f ;
struct City {
int idx , x ;
inline void input ( int _idx ) {
scanf ( "%d" , &x ) ;
idx = _idx ;
}
inline bool operator < ( const City &c ) const {
return x < c.x ;
}
} ;
City city[maxN] ;
int hash[maxN] , near[maxN] ;
int mmin[maxN << 2] ;
inline int max ( const int X , const int Y ) {
if ( X > Y ) return X ;
return Y ;
}
inline int min ( const int X , const int Y ) {
if ( X < Y ) return X ;
return Y ;
}
inline void swap ( int &X , int &Y ) {
int tmp = X ; X = Y ; Y = tmp ;
}
void Update ( int pos , int val , int l , int r , int o ) {
if ( l == r ) {
mmin[o] = val ;
return ;
}
int m = mid ;
if ( pos <= m ) Update ( pos , val , lson ) ;
else
Update ( pos , val , rson ) ;
mmin[o] = min ( mmin[ls] , mmin[rs] ) ;
}
int Query ( int L , int R , int l , int r , int o ) {
if ( L <= l && r <= R ) return mmin[o] ;
int m = mid ;
int ans = oo ;
if ( L <= m ) ans = min ( ans , Query ( L , R , lson ) ) ;
if ( m <
R ) ans = min ( ans , Query ( L , R , rson ) ) ;
return ans ;
}
void work () {
int n , m , l , r ;
while ( ~scanf ( "%d%d" , &n , &m ) ) {
clear ( mmin , oo ) ;
clear ( near , 0 ) ;
for ( int i = 1 ; i <= n ; ++ i ) city[i].input ( i ) ;
sort ( city + 1 , city + n + 1 ) ;
for ( int i = 1 ; i <= n ; ++ i ) hash[city[i].idx] = i ;
for ( int i = 1 ; i <= m ; ++ i ) {
scanf ( "%d%d" , &l , &r ) ;
l = hash[l] , r = hash[r] ;
if ( l > r ) swap ( l , r ) ;
near[r] = max ( near[r] , l ) ;
}
int pos = 0 , dp = 0 ;
//dp[i]表示处理到第i个点时前面所有的矛盾点都处理完毕的最小花费（包括i）
//此处直接用第i个位置的dp表示dp[i]
Update ( pos , dp , root ) ;
for ( int i = 1 ; i <= n ; ++ i ) {
pos = max ( near[i] , pos ) ;
if ( pos && i > 1 ) dp = Query ( pos , i - 1 , root ) ;
Update ( i , dp + city[i + 1].x - city[i].x , root ) ;
}
printf ( "%dn" , dp ) ;
}
}
int main () {
work () ;
return 0 ;
}