andyli

题解 UVA1479 【Graph and Queries】
本题只需要设计离线算法,因此可以把操作顺序反过来处理,先读入所有操作,执行所有的$D$操作得到最终的图,然后按照逆...
扫描右侧二维码阅读全文
22
2019/07

题解 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;
}
Last modification:November 6th, 2019 at 05:08 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment