题解 UVA1479 【Graph and Queries】

andyli

2019-07-22 21:35:06

Solution

本题只需要设计离线算法,因此可以把操作顺序反过来处理,先读入所有操作,执行所有的$D$操作得到最终的图,然后按照逆序把这些边逐步插入,并在恰当的时机执行$Q$和$C$操作。用一棵名次树($Treap$)维护一个连通分量中的点权,则$C$操作对应于名次树中的一次修改操作(可以用一次删除加一次输入来实现),$Q$操作对应$kth$(k小值)操作,而执行$D$操作时,如果两个端点已经是同一连通分量则无影响,否则将两个端点对应的两棵名次树合并。树合并的时间复杂度是多少呢?假设有两棵树$T_1$和$T_2$,结点数分别为$n_1$和$n_2$,若$n_1<n_2$,显然把$T_1$合并到$T_2$里比较高效,即把$T_1$中的所有结点一一插入到$T_2$中,时间复杂度为$O(n_1\log n_2)$。这样的策略叫启发式合并。如果使用启发式合并,对于任意结点来说,每当它被移动到新树中时该结点所在树的大小至少加倍。由于树的结点数不超过$n$,任意结点至多“被移动”$\log_2 n$次,而每次移动需要$O(\log n)$时间,因此总时间复杂度为$O(n\log^2 n)$。 完整代码如下: ```cpp #include <cstdio> #include <cstdlib> #include <iostream> #include <cstring> using namespace std; const int maxn = 20005, maxm = 60005, maxc = 500005; struct Node { Node* ch[2]; // 左右子树 int r, v, s; // 随机优先级,值,结点总数 Node(int v = 0) : v(v) { ch[0] = ch[1] = nullptr; r = rand(); s = 1; } void maintain() { s = 1; if (ch[0]) s += ch[0]->s; if (ch[1]) s += ch[1]->s; } int cmp(int x) const { return x == v ? -1 : x < v ? 0 : 1; } } * root[maxn]; void rotate(Node*& o, int d) { Node* k = o->ch[d ^ 1]; o->ch[d ^ 1] = k->ch[d]; k->ch[d] = o; o->maintain(); k->maintain(); o = k; } void insert(Node*& o, int x) { if (!o) o = new Node(x); else { int d = x < o->v ? 0 : 1; // 不要用cmp函数,因为可能会有相同结点 insert(o->ch[d], x); if (o->ch[d]->r > o->r) rotate(o, d ^ 1); } o->maintain(); } void remove(Node*& o, int x) { int d = o->cmp(x); if (d == -1) { Node* u = o; if (o->ch[0] && o->ch[1]) { int d2 = o->ch[0]->r > o->ch[1]->r; rotate(o, d2); remove(o->ch[d2], x); } else { if (o->ch[0] == nullptr) o = o->ch[1]; else o = o->ch[0]; delete u; } } else remove(o->ch[d], x); if (o) o->maintain(); } int kth(Node* o, int k) // 第k大的值 { if (!o || k <= 0 || k > o->s) return 0; int s = (o->ch[1] == nullptr ? 0 : o->ch[1]->s); if (k == s + 1) return o->v; if (k <= s) return kth(o->ch[1], k); return kth(o->ch[0], k - s - 1); } void mergeto(Node*& src, Node*& dest) { if (src->ch[0]) mergeto(src->ch[0], dest); if (src->ch[1]) mergeto(src->ch[1], dest); insert(dest, src->v); delete src; src = nullptr; } void removetree(Node*& x) { if (x->ch[0]) removetree(x->ch[0]); if (x->ch[1]) removetree(x->ch[1]); delete x; x = nullptr; } struct Command { char type; int x, p; // 根据type,p代表k或v Command(char type = 0, int x = 0, int p = 0) : type(type), x(x), p(p) {} } commands[maxc]; int weight[maxn], from[maxm], to[maxm], n, m; int f[maxn], query_cnt; bool vis[maxm]; long long query_tot; int find(int x) { return f[x] == x ? f[x] : f[x] = find(f[x]); } void AddEdge(int x) { int u = find(from[x]), v = find(to[x]); if (u != v) { if (root[u]->s > root[v]->s) swap(u, v); f[u] = v; mergeto(root[u], root[v]); } } void query(int x, int k) { query_cnt++; query_tot += kth(root[find(x)], k); } void change_weight(int x, int v) { int u = find(x); remove(root[u], weight[x]); insert(root[u], v); weight[x] = v; } int main() { int kase = 0; while (~scanf("%d%d", &n, &m) && n) { for (int i = 1; i <= n; i++) scanf("%d", &weight[i]); for (int i = 1; i <= m; i++) scanf("%d%d", &from[i], &to[i]); memset(vis, 0, sizeof(vis)); // 读命令 int c = 0; while (1) { char type; int x, p = 0, v = 0; cin >> type; if (type == 'E') break; scanf("%d", &x); if (type == 'D') vis[x] = true; else if (type == 'Q') scanf("%d", &p); else { scanf("%d", &v); p = weight[x]; weight[x] = v; } commands[c++] = Command(type, x, p); } // 最终的图 for (int i = 1; i <= n; i++) { f[i] = i; if (root[i]) removetree(root[i]); root[i] = new Node(weight[i]); } for (int i = 1; i <= m; i++) if (!vis[i]) AddEdge(i); // 反向操作 query_tot = query_cnt = 0; for (int i = c - 1; i >= 0; i--) { if (commands[i].type == 'D') AddEdge(commands[i].x); else if (commands[i].type == 'Q') query(commands[i].x, commands[i].p); else change_weight(commands[i].x, commands[i].p); } printf("Case %d: %.6lf\n", ++kase, query_tot * 1.0 / query_cnt); } return 0; } ```