「APIO2019」桥梁 题解

作者:神秘网友 发布时间:2020-07-15 16:11:00

「APIO2019」桥梁 题解

「APIO2019」桥梁 题解

先讲下部分分怎么搞。

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

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

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

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

(m Subtask 2) 是一个链的结构,发现问题转为 (maxlimits_{l,r,iin[l,r] & d_i>=w_j}{ r-l+1 })

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

(m Subtask 3,5)...不会做,告辞(

于是就可以收获 (43 m 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....

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

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

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

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

如果看不懂可以看代码,代码如下:

#include <bits/stdc++.h>
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<(const query &b) const { return val == b.val ? type < b.type : val > b.val; }
};
void merge(query *A, query *B, query *f, int n, int m) {
    int i = 1, j = 1, cnt = 0;
    while (i <= n && j <= m)
        if (A[i] < B[j])
            f[++cnt] = A[i++];
        else
            f[++cnt] = B[j++];
    while (i <= n) f[++cnt] = A[i++];
    while (j <= m) f[++cnt] = B[j++];
}
query a[N << 1], A[N << 1], B[N << 1], F[N << 1];
int type[N], b[N], r[N], s[N], w[N], ans[N], cnt;
int f[N], sz[N];
int find(int x) {
    while (x != f[x]) x = f[x];
    return x;
}
int st[N], top = 0;
void solve(int L, int R) {
    cnt = 0;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 1; i <= n; ++i) f[i] = i, sz[i] = 1;
    for (int i = L; i <= R; ++i)
        if (type[i] == 1)
            vis[b[i]] = i;
        else
            A[++cnt1] = query(1, w[i], i);
    sort(A + 1, A + cnt1 + 1);
    for (int i = 1; i <= m; ++i)
        if (vis[F[i].id] == 0)
            B[++cnt2] = F[i];
    merge(A, B, a, cnt1, cnt2);
    cnt = cnt1 + cnt2;
    for (int i = L; i <= R; ++i) vis[b[i]] = 0;
    for (int i = 1; i <= cnt; ++i) {
        // if(L==3) cout<<a[i].type<<" "<<a[i].id<<" "<<d[a[i].id]<<endl;
        if (a[i].type == 0) {
            int x = find(u[a[i].id]), y = find(v[a[i].id]);
            if (x == y)
                continue;
            if (sz[x] >= sz[y])
                swap(x, y);
            f[x] = y;
            sz[y] += sz[x];
        } else {
            top = 0;
            for (int j = L; j <= a[i].id; ++j)
                if (type[j] == 1)
                    vis[b[j]] = r[j];
            for (int j = L; j <= a[i].id; ++j)
                if (type[j] == 1 && vis[b[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 <= R; ++j)
                if (type[j] == 1 && d[b[j]] >= a[i].val && vis[b[j]] == 0) {
                    // if(i==3) cout<<j<<" Q
";
                    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];
                }
            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 <= a[i].id; ++j)
                if (type[j] == 1)
                    vis[b[j]] = 0;
        }
    }
    for (int i = L; i <= R; ++i)
        if (type[i] == 1)
            vis[b[i]] = 0;
}
int L[N], R[N];
int rd() {
    int x = 0;
    char ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - ‘0‘, ch = getchar();
    return x;
}
void write(int x) {
    if (x < 0)
        return putchar(‘-‘), write(-x);
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + ‘0‘);
}
int main() {
    n = rd();
    m = rd();
    for (int i = 1; i <= m; ++i) u[i] = rd(), v[i] = rd(), d[i] = rd();
    for (int i = 1; i <= m; ++i) F[i] = query(0, d[i], i);
    sort(F + 1, F + m + 1);
    int q;
    cin >> q;
    for (int i = 1; i <= q; ++i) {
        cin >> 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 <= cnt; ++i) L[i] = R[i - 1] + 1, R[i] = L[i] + len - 1;
    if (R[cnt] < q)
        ++cnt, L[cnt] = R[cnt - 1] + 1, R[cnt] = q;
    for (int i = 1; i <= cnt; ++i) {
        solve(L[i], R[i]);
        for (int j = L[i]; j <= R[i]; ++j)
            if (type[j] == 1)
                d[b[j]] = r[j];
        int cnt1 = 0, cnt2 = 0;
        for (int j = L[i]; j <= R[i]; ++j)
            if (type[j] == 1)
                vis[b[j]] = 1;
        for (int j = 1; j <= m; ++j)
            if (vis[F[j].id] == 0)
                A[++cnt1] = F[j];
            else
                B[++cnt2] = query(0, d[F[j].id], F[j].id);
        sort(B + 1, B + cnt2 + 1);
        merge(A, B, F, cnt1, cnt2);
        for (int j = L[i]; j <= R[i]; ++j)
            if (type[j] == 1)
                vis[b[j]] = 0;
    }
    for (int i = 1; i <= q; ++i)
        if (type[i] == 2)
            write(ans[i]), putchar(‘
‘);
    return 0;
}

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

「APIO2019」桥梁 题解

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

「APIO2019」桥梁 题解相关教程

  1. deepin chrome代理出现问题 mangoogle-chrome-stable 问题解决
  2. 安装包release版出现闪退问题解决及CalendarView的使用
  3. LeetCode338. Counting Bits题解
  4. Docker pull慢,无法pull问题解决(更改镜像源为阿里云国内镜像)
  5. python27 in win10出现编码问题解决方案
  6. Codeforces Round #668 (Div. 1) 题解
  7. Leetcode题11、盛水最多的容器(Python题解)
  8. NettyTCP粘包/拆包问题解决之道