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

在X轴上有这样一个国家——风之国。风之国虽然是一个国家，但是却有N个首领，每个首领管辖着各自的一个城市。曾几何时，风之国是非常和睦的国家，可是现在突然出现了一个奶茶妹子，各个城市的首领为了这个妹子，掀起了一场没有妹子，就没有夜晚的战争。
这N个城市坐落于X轴上的一些不重复的点上，并且每个城市都只与其左右相邻的城市相互连通。所以一共会有N-1条道路。战争之前任意两个城市之间可以自由贸易。后来因为这场战争，有K对城市由于重要战略物资不允许连通。
X神（掌管X轴的大神）发现了这一点，试图想利用他的法力来破坏一些道路，使得这K对城市两两之间都无法相互连通。
由于破坏每条道路所消耗的法力可能是不一样的，破坏某条道路所消耗的法力是该道路连通的两个城市之间的距离。所以X神想知道最少需要消耗多少的法力，能够使得这K对城市两两之间不能连通。

输入包含多少数据，对于每组数据：
第一行：N K，表示N个城市，K对不允许连通的城市。(2<=N<=100000，0<=K<=100000)。
接下来一行有N个数字x1, x2, x3......xN，其中xi表示第i个城市在X轴上的位置。且每个城市都在不同的位置上。(1<=xi<=10^9, 1<=i<= N)。
接下来K行：u v，表示城市u和城市v不允许连通。输入可能存在重复。(1<=u,v<=n , 且u!=v)

输出一个数，表示X神至少需要消耗多少的法力来破坏一些路，使得这K对城市之间都彼此不连通。

3 3
63 0 132
2 3
1 3
2 1
3 2
63 0 132
2 3
1 2

132
63

对于第二组数据：

        城市2和城市3 不允许连通，

        城市1和城市2 不允许连通，

        然而对于城市1和城市3没有要求，可连通，可不连通。

#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 ( "%d\n" , dp ) ;}
}int main () {work () ;return 0 ;
}