HDU3726---Graph and Queries 离线处理+Treap
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3726
题意：n个点m条边的一张无向图，每个点有一个权值， 有3中操作。
D X 删除第X条边
Q X K 计算与X点相连所有点中第k大的权值
C X V把X的权值改为 V
输出 Q次询问的平均值
大白上的例题， 离线处理，把所有操作 反过来处理，，这样删边变成了 加边，，瞬间好处理多了。。细节也有很多。
1 #include <set> 2 #include <map> 3 #include <cmath> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstdlib> 11 #include <cstring> 12 #include <iostream> 13 #include <algorithm> 14 using namespace std; 15 typedef unsigned long long ull; 16 typedef long long ll; 17 const int inf = 0x3f3f3f3f; 18 const double eps = 1e-8; 19 const int maxn = 2e4+10; 20 int n, m, val[maxn]; 21 int pa[maxn]; 22 void init() 23 { 24 for (int i = 0; i <= n; i++) 25 { 26 pa[i] = i; 27 } 28 } 29 int find(int x) 30 { 31 return pa[x] = (pa[x] == x ? x : find(pa[x])); 32 } 33 struct Node 34 { 35 Node* ch[2]; 36 int key, r, siz; 37 Node (int x) 38 { 39 key = x; 40 siz = 1; 41 ch[0] = ch[1] = NULL; 42 r = rand(); 43 } 44 bool operator < (const Node &rhs)const 45 { 46 return r < rhs.r; 47 } 48 int cmp(int x) 49 { 50 if (x == key) 51 return -1; 52 return x < key ? 0 : 1; 53 } 54 void maintain() 55 { 56 siz = 1; 57 if (ch[0] != NULL) 58 siz += ch[0] -> siz; 59 if (ch[1] != NULL) 60 siz += ch[1] -> siz; 61 } 62 }; 63 void rotate(Node* &root, int d) 64 { 65 Node* tmp = root -> ch[d^1]; 66 root -> ch[d^1] = tmp -> ch[d]; 67 tmp -> ch[d] = root; 68 root -> maintain(); 69 tmp -> maintain(); 70 root = tmp; 71 } 72 void insert(Node* &root, int x) 73 { 74 if (root == NULL) 75 root = new Node (x); 76 else 77 { 78 int d = x < root -> key ? 0 : 1; 79 insert (root ->ch[d], x); 80 if (root -> ch[d] -> r > root -> r) 81 rotate(root, d^1); 82 83 } 84 root -> maintain(); 85 } 86 void dele(Node* &root, int x) 87 { 88 int d = root -> cmp(x); 89 if (d == -1) 90 { 91 Node* tmp = root; 92 if (root -> ch[0] != NULL && root -> ch[1] != NULL) 93 { 94 int d1 = (root -> ch[0] -> r > root -> ch[1] -> r ? 0 : 1); 95 rotate(root, d1^1); 96 dele(root -> ch[d1^1], x); 97 } 98 else 99 { 100 if (root -> ch[0] == NULL) 101 root = root -> ch[1]; 102 else 103 root = root -> ch[0]; 104 delete tmp; 105 } 106 } 107 else 108 dele(root->ch[d], x); 109 if (root != NULL) 110 root -> maintain(); 111 } 112 int Get_kth(Node* root, int k) 113 { 114 if (root == NULL || k <= 0 || root -> siz < k) 115 return 0; 116 int s = root -> ch[1] == NULL ? 0 : root -> ch[1] -> siz; 117 if (s + 1 == k) 118 return root -> key; 119 if (s + 1 > k) 120 return Get_kth(root -> ch[1], k); 121 else 122 return Get_kth(root -> ch[0], k-s-1); 123 124 } 125 Node* root[maxn]; 126 void merge_tree(Node* &src, Node* &fa) 127 { 128 if (src -> ch[0] != NULL) 129 merge_tree(src -> ch[0], fa); 130 if (src -> ch[1] != NULL) 131 merge_tree(src -> ch[1], fa); 132 insert(fa, src -> key); 133 delete src; 134 src = NULL; 135 } 136 void remove_tree(Node* &root) 137 { 138 if (root -> ch[0] != NULL) 139 remove_tree(root -> ch[0]); 140 if (root -> ch[1] != NULL) 141 remove_tree(root -> ch[1]); 142 delete root; 143 root = NULL; 144 } 145 struct 146 { 147 int x, y; 148 bool is_del; 149 } e[3 * maxn]; 150 struct 151 { 152 int type, x, p; 153 } Q[maxn*25]; 154 void add_edge(int idx) 155 { 156 int fx = find(e[idx].x); 157 int fy = find(e[idx].y); 158 if (fx != fy) 159 { 160 if (root[fx] -> siz > root[fy] -> siz) 161 { 162 pa[fy] = fx; 163 merge_tree(root[fy], root[fx]); 164 } 165 else 166 { 167 pa[fx] = fy; 168 merge_tree(root[fx], root[fy]); 169 170 } 171 } 172 173 } 174 int main(void) 175 { 176 #ifndef ONLINE_JUDGE 177 freopen("in.txt","r",stdin); 178 #endif 179 int cas = 1; 180 while (~ scanf ("%d%d",&n, &m)) 181 { 182 if (n == 0 && m == 0) 183 break; 184 for (int i = 0; i < n; i++) 185 { 186 scanf ("%d", val + 1 + i); 187 } 188 for (int i = 1; i <= m; i++) 189 { 190 scanf ("%d%d", &e[i].x, &e[i].y); 191 e[i].is_del = false; 192 } 193 char op[5]; 194 int tot = 0; 195 while (scanf ("%s",op) && op[0] != 'E') 196 { 197 if (op[0] == 'D') 198 { 199 scanf ("%d", &Q[tot].x); 200 Q[tot++].type = 0; 201 e[Q[tot-1].x].is_del = true; 202 } 203 if (op[0] == 'Q') 204 { 205 scanf ("%d%d", &Q[tot].x, &Q[tot].p); 206 Q[tot++].type = 1; 207 } 208 if (op[0] == 'C') 209 { 210 int v; 211 scanf ("%d%d", &Q[tot].x, &v); 212 Q[tot].p = val[Q[tot].x]; 213 val[Q[tot].x] = v; 214 Q[tot++].type = 2; 215 } 216 } 217 init(); 218 for (int i = 0; i < n; i++) 219 { 220 if (root[i+1] != NULL) 221 remove_tree(root[i+1]); 222 root[i+1] = new Node (val[i+1]); 223 } 224 for (int i = 0; i < m; i++) 225 { 226 if (e[i+1].is_del == false) 227 add_edge(i+1); 228 } 229 ll ans1 = 0, ans2 = 0; 230 for (int i = tot - 1; i >= 0; i--) 231 { 232 if (Q[i].type == 0) 233 { 234 add_edge(Q[i].x); 235 } 236 if (Q[i].type == 1) 237 { 238 ans1 += Get_kth(root[find(Q[i].x)], Q[i].p); 239 ans2 ++; 240 } 241 if (Q[i].type == 2) 242 { 243 int father = find(Q[i].x); 244 dele (root[father], val[Q[i].x]); 245 insert (root[father], Q[i].p); 246 val[Q[i].x] = Q[i].p; 247 } 248 } 249 printf("Case %d: %.6f ", cas++, 1.0*ans1 / ans2); 250 } 251 return 0; 252 }