「APIO2019」桥梁 题解

标签：怎么   swap   ack   数据结构   问题   写代码   ace   har   col   

先讲下部分分怎么搞。

有个非常暴力的暴力做法：

对于每一个询问，把边权大于 \(w_j\) 的边加入，并查集维护联通块即可。

时间复杂度 \(\mathcal{O(qm)}\)，可以过 \(\mathrm{Subtask\ 1}\)

当 \(t_i=2\) 的时候，可以直接 kruskal 重构树，可以过 \(\mathrm{Subtask \ 4}\)

\(\rm Subtask \ 2\) 是一个链的结构，发现问题转为 \(\max\limits_{l,r,i\in[l,r] \& d_i>=w_j}\{ r-l+1 \}\)

然后就可以用线段树做一下。

\(\rm Subtask \ 3,5\)...不会做，告辞（

于是就可以收获 \(43 \rm pts\)

至于正解...

可以把询问分块，设块长为 \(S\)，把每一条边分成三种去做，一种是块内没修改过的，一种是块内修改过，时间在询问前的，另一种是块内修改过，时间在询问后的。

前一种边可以直接与询问排序去做，时间复杂度 \(\mathcal O(\frac{q}{S}m \log m)\)

第二种边，第三种边可以枚举块内修改，用可撤销化并查集去做，时间复杂度是 \(\mathcal O(\frac{q}{S}S^2 \log n)\)

至于块长多大最优，人肉二分得出好像是 \(\sqrt{m \log n}\)

交 LOJ ，直接 AC 了，然后再交洛谷，TLE 44 pts....

神 \(\sf\color{black}{F}\color{red}{zzzz}\) 说这题还有两个优化，看了一眼题解，发现第一种边在排序的时候完全可以先排序再归并，流程如下：

1. 在解决询问之前先把边排序一遍
2. 把排序后的边塞进块里解决询问，把询问排序，没修改的边拉出来和询问做一次归并排序，时间复杂度 \(\mathcal{O(\frac{q}{S}m)}\)
3. 解决当前块内的询问后，把块内修改的边拉出来排序，没有修改的边也拉出来，和修改的边做一次归并排序，时间复杂度 \(\mathcal{O}(\frac{q}{S}m)\)

看起来好像优化了时间复杂度但其实只是卡常，因为时间复杂度主要在可撤销化并查集上...

总而言之这题是一道不错的数据结构题，也许能放进 NOIP 提高组并查集讲课里（

如果看不懂可以看代码，代码如下：

#include 
using namespace std;
const int N = 1e5 + 5;
int u[N], v[N], d[N], vis[N], n, m;
struct query {
    int type, val, id;
    query() {}
    query(int _t, int _v, int _id) {
        type = _t;
        val = _v;
        id = _id;
    }
    bool operator b.val; }
};
void merge(query *A, query *B, query *f, int n, int m) {
    int i = 1, j = 1, cnt = 0;
    while (i = sz[y])
                swap(x, y);
            f[x] = y;
            sz[y] += sz[x];
        } else {
            top = 0;
            for (int j = L; j = a[i].val) {
                    int x = find(u[b[j]]), y = find(v[b[j]]);
                    if (x == y)
                        continue;
                    if (sz[x] >= sz[y])
                        swap(x, y);
                    st[++top] = x;
                    f[x] = y;
                    sz[y] += sz[x];
                }
            for (int j = a[i].id; j = a[i].val && vis[b[j]] == 0) {
                    // if(i==3) cout= sz[y])
                        swap(x, y);
                    st[++top] = x;
                    f[x] = y;
                    sz[y] += sz[x];
                }
            int x = find(s[a[i].id]);
            ans[a[i].id] = sz[x];
            while (top > 0) sz[f[st[top]]] -= sz[st[top]], f[st[top]] = st[top], --top;
            for (int j = L; j  9)
        write(x / 10);
    putchar(x % 10 + ‘0‘);
}
int main() {
    n = rd();
    m = rd();
    for (int i = 1; i > q;
    for (int i = 1; i > type[i];
        if (type[i] == 1)
            b[i] = rd(), r[i] = rd();
        else
            s[i] = rd(), w[i] = rd();
    }
    int len = 1000, cnt = q / len;
    for (int i = 1; i 

对于我来说，这题是典型的口胡 3 分钟，写代码 3 小时 /kk

「APIO2019」桥梁 题解

标签：怎么   swap   ack   数据结构   问题   写代码   ace   har   col   

原文地址：https://www.cnblogs.com/limit-ak-ioi/p/13304994.html