http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=509&page=show_problem&problem=4225

思路:离线+逆序操作。逆序后删边变连边,用并查集判连通性即可。Q操作用名次树解决,C操作拆为删除和插入两个操作。
顺便附上我的Treap+名次树模板。

/*0.975s*/

const int mxc = int(5e5) + 5;
const int mxn = int(2e4) + 5;
const int mxm = int(6e4) + 5;

struct node
{
    node *ch[2]; /// 左右子树
 int pri, v; /// 优先级(最大堆), 值
 int sz; /// 以该节点为根的子树节点总数
 node(int v): v(v) {ch[0] = ch[1] = NULL; pri = rand(); sz = 1;}
    bool operator < (const node &b) const
    {
        return pri < b.pri;
    }
    bool operator > (const node &b) const
    {
        return pri > b.pri;
    }
    int cmp(const int x) const
    {
        return x == v ? -1 : x > v;
    }
    void maintain() /// 维护(名次树上)该节点的sz
 {
        sz = 1;
        if (ch[0]) sz += ch[0]->sz;
        if (ch[1]) sz += ch[1]->sz;
    }
} *root[mxn];

void clear(node *&o) /// 入口为root
{
    if (o->ch[0]) clear(o->ch[0]);
    if (o->ch[1]) clear(o->ch[1]);
    delete o; /// 释放new出来的空间
 o = NULL; /// *对于每个节点都可能是根节点的Treap,这句话是必须要的
}

void rotate(node *&o, int d) /// d=0左旋, d=1右旋
{
    node *k = o->ch[!d]; /// 把逆旋转方向侧的儿子k提上来, o顺着旋转方向变为k的儿子
 o->ch[!d] = k->ch[d]; /// 即o->ch[!d] = o->ch[!d]->ch[d];
 k->ch[d] = o;
    o->maintain(), k->maintain();
    o = k; /// 修改指针指向的位置,从而完成旋转
}

void insert(node *&o, int x) /// *若为set, 调用前先判断find(root, x);
{
    if (o == NULL) o = new node(x);
    else
    {
        int d = (x > o->v); /// *允许相同的节点值
     insert(o->ch[d], x);
        if (o->ch[d] > o) rotate(o, !d); /// 如果子树的优先级高,那就提上去
 }
    o->maintain();
}

void erase(node *&o, int x) /// *若不保证Treap中有x, 调用前请判断find(root, x);
{
    int d = o->cmp(x);
    if (~d) erase(o->ch[d], x);
    else
    {
        if (o->ch[0] == NULL) o = o->ch[1];
        else if (o->ch[1] == NULL) o = o->ch[0]; /// 只有一颗子树,直接用子树替代即可
     else
        {
            d = (o->ch[0] > o->ch[1]);
            rotate(o, d), erase(o->ch[d], x); /// 旋转优先级高的上去,再递归删除
     }
    }
    if (o) o->maintain();
}

void merge(node *&from, node *&to) /// O(nlog^2(n))合并两棵Treap, 调用时注意顺序
{
    if (from->ch[0]) merge(from->ch[0], to);
    if (from->ch[1]) merge(from->ch[1], to);
    insert(to, from->v);
    delete from;
    from = NULL;
}

int kthl(node *o, int k) /// 找第k小的值(less)
{
    if (o == NULL || k <= 0 || k > o->sz) return 0; /// *无效查询
 int sz = (o->ch[0] ? o->ch[0]->sz : 0);
    if (k == sz + 1) return o->v;
    if (k <= sz) return kthl(o->ch[0], k);
    return kthl(o->ch[1], k - (sz + 1));
}

int kthg(node *o, int k) /// 找第k大的值(greater)
{
    if (o == NULL || k <= 0 || k > o->sz) return 0; /// *无效查询
 int sz = (o->ch[1] ? o->ch[1]->sz : 0);
    if (k == sz + 1) return o->v;
    if (k <= sz) return kthg(o->ch[1], k);
    return kthg(o->ch[0], k - (sz + 1));
}

int rankl(node *o, int x) /// 找值x的小序名次,即比x小的节点数+1
{
    if (o == NULL) return 1;
    int d = o->cmp(x), sz = (o->ch[0] ? o->ch[0]->sz + 1 : 1);
    if (d == -1) return sz;
    if (d) return sz + rankl(o->ch[1], x);
    return rankl(o->ch[0], x);
}

int rankg(node *o, int x) /// 找值x的大序名次,即比x大的节点数+1
{
    if (o == NULL) return 1;
    int d = o->cmp(x), sz = (o->ch[1] ? o->ch[1]->sz + 1 : 1);
    if (d == -1) return sz;
    if (d) return rankl(o->ch[1], x);
    return sz + rankl(o->ch[0], x);
}

/*模板end*/

struct Cmd
{
    char op; /// 当op=='D'时, p未用到
 int x, p;
} cmd[mxc];

int w[mxn], from[mxm], to[mxm], removed[mxm], fa[mxn];
char op[2];

int find(int x) {return ~fa[x] ? fa[x] = find(fa[x]) : x;}

void add_edge(int x) /// 该函数相当于并查集的merge(from[x], to[x])
{
    int u = find(from[x]), v = find(to[x]);
    if (u != v) /// 启发式合并Treap
 {
        if (root[u]->sz < root[v]->sz) fa[u] = v, merge(root[u], root[v]);
        else fa[v] = u, merge(root[v], root[u]);
    }
}

void change_weight(int o, int v) /// 修改边的权值
{
    int u = find(o);
    erase(root[u], w[o]);
    insert(root[u], v); /// 把修改操作分解为删除和插入
 w[o] = v;
}

void init(int n)
{
    mem(fa, -1);
    int i;
    Forr(i, 1, n + 1)
    {
        if (root[i]) clear(root[i]);
        root[i] = new node(w[i]);
    }
}

void build(int m)
{
    int i;
    Forr(i, 1, m + 1) if (!removed[i]) add_edge(i); /// 建Treap:*若有这条边则加进去
}

int main()
{
    int cas = 0, cnt, n, m, i, x, p, v, cntq;
    ll sum;
    while (SII(n, m), n)
    {
        Pcas();
        SA(w + 1, i, n);
        Forr(i, 1, m + 1) SII(from[i], to[i]);
        mem(removed, 0);
        cnt = 0;
        while (SS(op), op[0] != 'E')
        {
            if (op[0] == 'D') SI(x), removed[x] = true;
            else if (op[0] == 'Q') SII(x, p);
            else SII(x, v), p = w[x], w[x] = v; /// 注意记录的顺序
         cmd[cnt++] = (Cmd) {op[0], x, p};
        }
        init(n);
        build(m);
        /// 现在图为最终状态, 然后反向操作
     sum = 0LL, cntq = 0;
        rFor(i, cnt - 1)
        {
            if (cmd[i].op == 'D') add_edge(cmd[i].x);
            else if (cmd[i].op == 'Q') ++cntq, sum += (ll)kthg(root[find(cmd[i].x)], cmd[i].p);
            else change_weight(cmd[i].x, cmd[i].p);
        }
        PD((double)sum / cntq);
    }
    return 0;
}

Comments

comments powered by Disqus