题解 UVA1479 【Graph and Queries】

本题只需要设计离线算法，因此可以把操作顺序反过来处理，先读入所有操作，执行所有的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)。
完整代码如下：

#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;
}