G - 风之国
Problem Description
在X轴上有这样一个国家——风之国。风之国虽然是一个国家，但是却有N个首领，每个首领管辖着各自的一个城市。曾几何时，风之国是非常和睦的国家，可是现在突然出现了一个奶茶妹子，各个城市的首领为了这个妹子，掀起了一场没有妹子，就没有夜晚的战争。
这N个城市坐落于X轴上的一些不重复的点上，并且每个城市都只与其左右相邻的城市相互连通。所以一共会有N-1条道路。战争之前任意两个城市之间可以自由贸易。后来因为这场战争，有K对城市由于重要战略物资不允许连通。
X神（掌管X轴的大神）发现了这一点，试图想利用他的法力来破坏一些道路，使得这K对城市两两之间都无法相互连通。
由于破坏每条道路所消耗的法力可能是不一样的，破坏某条道路所消耗的法力是该道路连通的两个城市之间的距离。所以X神想知道最少需要消耗多少的法力，能够使得这K对城市两两之间不能连通。
Input
输入包含多少数据，对于每组数据：
第一行：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)
Output
输出一个数，表示X神至少需要消耗多少的法力来破坏一些路，使得这K对城市之间都彼此不连通。
Sample Input
3 3 63 0 132 2 3 1 3 2 1 3 2 63 0 132 2 3 1 2
Sample Output
132 63
Hint
对于第二组数据：
城市2和城市3 不允许连通，
城市1和城市2 不允许连通，
然而对于城市1和城市3没有要求，可连通，可不连通。
G题
时间复杂度：O(N*logN)
方法一：
先对所有点按照x排下序。然后再把k对矛盾点映射为排序后的下标。
然后就是一个dp
Dp[i]表示i前面（包括i）处理掉所有矛盾点的最小花费。
然后状态转移时dp[j] = min( dp[i] + len(i, i + 1) )..
其中a <= i< j。len(i, i + 1)是i与i+1之间的距离， a是j点前面最大的矛盾起点。
求最小值可以用线段树处理。
求出j点dp值之后，把dp[j] + len(j, j + 1)插入到线段树中j位置。
方法二：（YY乱搞版）
同样先对所有点按照x排下序。然后再把这K对矛盾点映射为排序后的下标(u,v)，并使得u<v，然后对这k对矛盾按照右端点v进行从小到大排个序。
然后就是一个乱搞yy的过程。
对于排序后的K对矛盾，按照顺序进行下列步骤：
第一步：求其不允许连通的两个点路径上的最小边，记为Min_E ；
第二步：然后 Ans+=Min_E ；
第三步：再把路径上所有的边的权值都减去最小边的权值。
如此，处理完K对矛盾后，Ans就是答案。
经过我100W的数据对拍，由此得证该方法的正确性！O(∩_∩)O~
|
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#include#include#includeusing#define#defineconstconstinline(int{ char boolfalse; while((in=getchar())!=EOF'9''0')'-'); if(in==EOF) return else(in=='-')true,num=0; else '0'; while(in=getchar(),in>='0''9')'0'; if(neg) return}struct int voidintintint dp[rt] if(lreturn; int build(lson); } voidintintintintint if(l dp[rt] return; } int if(x else dp[rt] } intintintintintint if(ll return } int int if(ll if(rr return }};struct int inlineint //scanf(x); scanf("%d", idx } inlineconstconst return }};SegTreeintcityintintvoid tree.build(0, memset(pre,sizeof(pre));}int //freopen("wind.in", //freopen("wind.out", while(~scanf("%d%d", init(); for(int c[i].input(i); } sort(c for(int mp[ } for(int int scanf("%d%d", //scanf(a); a if(a pre[b] } tree.update(0, int int for(int if(pre[i] lim } dp tree.update(i, } printf("%d\n", }} |