题意：有n个星球(编号0到n-1)，有些星球之间有路径相连，且每个星球都有一个power值。每个星球可以求助，它会选择与它直接或间接相连的星球里power值最大的一个(如果有power最大且相等的几个星球，选择编号最小的一个星球)，如果那个星球的power值比自己大，则向其求助，否则不能求助。现在，给出两种操作query a和destroy a b，前者的意思是问星球a会向哪个星球求助(不能求助输出-1)，后者的意思是毁坏星球a和星球b之间直接连接的路径。(n <= 10^4，m <= 2*10^4，操作个数 <= 5*10^4)
解法：如果正着想很难做，但如果倒着想就很容易了。即，先将所有指令读入并保存，然后将所有指令要毁坏的路径全部毁坏，然后从最后一个指令开始操作，若指令为query则求a可以向谁求助，若指令为destroy a b则重建星球a和星球b之间的路径。这样，就是一个很裸的并查集了。
由于数据范围太大，所以在读入所有指令毁坏指定边的时候，暴力会TLE。我得解决方法是，将所有连接的边保存并排序，对每条边设置一个变量表示这条边存在还是已经毁坏了，然后每次要毁坏都用二分查找。
tag:并查集, good
1 /* 2 * Author: Plumrain 3 * Created Time: 2013-11-28 20:27 4 * File Name: DS-ZOJ-3261.cpp 5 */ 6 #include <iostream> 7 #include <cstdio> 8 #include <algorithm> 9 #include <vector> 10 11 using namespace std; 12 13 #define PB push_back 14 const int maxn = 10005; 15 const int maxm = 20005; 16 17 struct node{ 18 int f, r; 19 }; 20 21 struct query{ 22 int s, e; 23 int q; 24 }; 25 26 struct Pat{ 27 int s, e; 28 bool x; 29 }; 30 31 int n, m, q; 32 int cost[maxn]; 33 Pat pat[maxm]; 34 vector<int> ans; 35 query ask[maxn*5]; 36 node nod[maxn]; 37 38 bool cmp(Pat a, Pat b) 39 { 40 return a.s < b.s || (a.s == b.s && a.e < b.e); 41 } 42 43 bool les(int x, int y) 44 { 45 Pat tmp; 46 tmp.s = ask[y].s; tmp.e = ask[y].e; 47 return cmp(pat[x], tmp); 48 } 49 50 int bin_search(int x) 51 { 52 int l = 0, r = m-1; 53 while (l <= r){ 54 int mid = (l + r) >> 1; 55 if (les(mid, x)) l = mid + 1; 56 else r = mid - 1; 57 } 58 return l; 59 } 60 61 void pat_del(int x) 62 { 63 int pos = bin_search(x); 64 pat[pos].x = 0; 65 } 66 67 void init() 68 { 69 for (int i = 0; i < n; ++ i) 70 scanf ("%d", &cost[i]); 71 72 scanf ("%d", &m); 73 for (int i = 0; i < m; ++ i){ 74 scanf ("%d%d", &pat[i].s, &pat[i].e); 75 if (pat[i].s > pat[i].e) swap(pat[i].s, pat[i].e); 76 pat[i].x = 1; 77 } 78 79 sort(pat, pat+m, cmp); 80 81 scanf ("%d", &q); 82 char s[10]; 83 for (int i = 0; i < q; ++ i){ 84 scanf ("%s", s); 85 if (s[0] == 'q'){ 86 ask[i].q = 0; 87 scanf ("%d", &ask[i].s); 88 } 89 else{ 90 scanf ("%d%d", &ask[i].s, &ask[i].e); 91 if (ask[i].s > ask[i].e) swap(ask[i].s, ask[i].e); 92 pat_del(i); 93 ask[i].q = 1; 94 } 95 } 96 } 97 98 int find(int x) 99 { 100 if (x != nod[x].f){ 101 nod[x].f = find(nod[x].f); 102 int tmp; 103 if (cost[nod[x].r] > cost[nod[nod[x].f].r]) tmp = nod[x].r; 104 else if (cost[nod[x].r] == cost[nod[nod[x].f].r]) tmp = min(nod[x].r, nod[nod[x].f].r); 105 else tmp = nod[nod[x].f].r; 106 nod[x].r = nod[nod[x].f].r = tmp; 107 } 108 return nod[x].f; 109 } 110 111 void merge(int s, int e, int t1, int t2) 112 { 113 nod[t1].f = t2; 114 int tmp; 115 if (cost[nod[t1].r] > cost[nod[t2].r]) tmp = nod[t1].r; 116 else if (cost[nod[t1].r] == cost[nod[t2].r]) tmp = min(nod[t1].r, nod[t2].r); 117 else tmp = nod[t2].r; 118 nod[t1].r = nod[t2].r = tmp; 119 } 120 121 void gao() 122 { 123 for (int i = 0; i < n; ++ i) 124 nod[i].r = nod[i].f = i; 125 126 for (int i = 0; i < m; ++ i) if (pat[i].x){ 127 int s = pat[i].s, e = pat[i].e; 128 int t1 = find(s), t2 = find(e); 129 if (t1 != t2) 130 merge(s, e, t1, t2); 131 } 132 133 for (int i = q-1; i >= 0; -- i){ 134 if (ask[i].q == 0){ 135 int tmp = ask[i].s; 136 int y = find(tmp); 137 int tmp2 = nod[y].r; 138 if (cost[tmp2] <= cost[tmp]) ans.PB (-1); 139 else ans.PB (tmp2); 140 } 141 if (ask[i].q == 1){ 142 int s = ask[i].s, e = ask[i].e; 143 int t1 = find(s), t2 = find(e); 144 if (t1 != t2) 145 merge(s, e, t1, t2); 146 } 147 } 148 } 149 150 int main() 151 { 152 bool flag = 0; 153 while (scanf ("%d", &n) != EOF){ 154 if (flag) printf (" "); 155 flag = 1; 156 157 init(); 158 ans.clear(); 159 gao(); 160 161 int sz = ans.size(); 162 for (int i = sz-1; i >= 0; -- i) 163 printf ("%d ", ans[i]); 164 } 165 return 0; 166 }