2024 ICPC 昆明邀请赛

比赛链接

Problems	AC
A. Two-star Contest	○
B. Gold Medal	○
C. Stop the Castle 2
D. Generated String
E. Relearn through Review	⊕
F. Collect the Coins	待补
G. Be Positive	○
H. Subarray
I. Left Shifting 2	○
J. The Quest for El Dorado	⊕
K. Permutation
L. Trails	⊕
M. Italian Cuisine	待补

E gcd 的性质

给定一个长为 n 的数列 a[n], 和一个非负整数 k。
可以至多一次 选择数列的一个区间 +k
求最大化的序列 gcd 和

赛时盯着这道题盯了一个小时然后写了个假算法

赛时想到了 gcd 是单调不增的，也想到了 gcd 最多会减少 logX 次

一段数同时加上 k 以后，gcd 和他们的差有关

明明都知道了这三个关键的性质，还是没得出正解。

假如把整个序列写成一个柿子，答案就非常明了了

$ \gcd(a[1]…a[n]) = $

$\gcd(\gcd(a[1]…a[l - 1]), \gcd(\left|a[l] - a[l + 1]\right|
…\left|a[r - 1] - a[r]\right|), a[r] + k, \gcd(a[r + 1]…a[n])) $

假如 r 确定，则后两项都确定了。至于前两项，都只和原数组有关。

至于原数组，结合 gcd 前缀只有 logX 个的性质，本质不同的只有 logX 个，枚举 logX 个分界点即可

note：注意 ans 的初值

void solve() {
    int n = read(), k = read();

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        a[i] = read();
    }

    vector<int> pre(n + 1), suf(n + 2);
    for (int i = 1; i <= n; i++) {
        pre[i] = std::__gcd(pre[i - 1], a[i]);
    }
    for (int i = n; i >= 1; i--) {
        suf[i] = std::__gcd(suf[i + 1], a[i]);
    }

    int ans = pre[n];

    for (int i = 1; i <= n; i++) {
        if (pre[i] == pre[i - 1]) continue;

        int g = 0;

        for (int j = i; j <= n; j++) {
            g = std::__gcd(g, a[j] + k);
            ans = max(ans, std::__gcd(pre[i - 1], std::__gcd(g, suf[j + 1])));
        }
    }
    cout << ans << '\n';
}

J 最短路 RMQ

给一张无向图，每条边有长度和颜色。从节点 $1$ 开始一共要走 $k$ 轮，每一轮可以一次性走完颜色均为 $a_i$ 且总长不超过 $b_i$ 的边。问 $k$ 轮走完以后能走到哪些点。
$n, m, k \le 5 \times 10^5$

以走到了第 r 轮为第一关键字，这一轮走了距离 d 为第二关键字，作为最短路的距离。

当拓展一条边 (c, len) 时如果 $c = a_r$ 且 $d + len \le b_r$，则可以直接转移。

否则需要在 $[r + 1, k]$ 中找一个颜色为 $c$ 的且 $b_nr \ge len$ 的最早的一个 $nr$ 转移过去。

每个颜色开个 rmq，在 rmq 上二分即可。

复杂度 $O(m (\log{m} + \log{k}) + k \log k)$

void solve() {
    int n = read(), m = read(), k = read();

    vector g(n + 1, vector<array<int, 3>>());
    for (int i = 1; i <= m; i++) {
        int u = read(), v = read();
        int c = read(), w = read();

        g[u].pb({v, c, w});
        g[v].pb({u, c, w});
    }

    vector<std::array<int, 2>> tik(k + 1);

    vector rmq(m + 1, vector(21, vector<int>()));
    vector pos(m + 1, vector<int>());

    for (int i = 1; i <= k; i++) {
        tik[i][0] = read();
        tik[i][1] = read();

        rmq[tik[i][0]][0].eb(tik[i][1]);
        pos[tik[i][0]].eb(i);
    }

    for (int c = 1; c <= m; c++) {
        for (int j = 1; j <= 20; j++) {
            rmq[c][j].assign(rmq[c][0].size() + 1, 0);
        } 
    }
 
    for (int c = 1; c <= m; c++) {
        for (int j = 1; j <= 20; j++) {
            for (int i = 0; i + (1 << j) - 1 < rmq[c][0].size(); i++) {
                rmq[c][j][i] = max(rmq[c][j - 1][i], rmq[c][j - 1][i + (1 << (j - 1))]);
            }
        }
    }

    auto getrmq = [&](int c, int l, int r) {
        int k = std::__lg(r - l + 1);
        return max(rmq[c][k][l], rmq[c][k][r - (1 << k) + 1]);
    };

    auto search = [&](int l, int c, int len) {
        if (pos[c].empty() or pos[c].back() < l) return -1;

        l = std::lower_bound(pos[c].begin(), pos[c].end(), l) - pos[c].begin();

        int res = -1;
        for (int r = rmq[c][0].size() - 1; l <= r; ) {
            int mid = l + r >> 1;
            if (getrmq(c, l, mid) >= len) {
                res = mid, r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        
        if (res == -1) return -1;
        return pos[c][res];
    };

    vector<int> vis(n + 1);
    vector<array<int, 2>> dis(n + 1, {inf, inf});
    std::priority_queue<array<int, 3>, vector<array<int, 3>>, std::greater<>> q;

    dis[1] = {1, 0};
    q.push({1, 0, 1});
    while (!q.empty()) {
        auto [r, d, u] = q.top();
        q.pop();

        if (vis[u]) continue;
        vis[u] = 1;

        for (auto [v, c, len] : g[u]) {
            if (tik[r][0] == c and tik[r][1] >= d + len) {
                if (dis[v][0] > r or dis[v][0] == r and dis[v][1] > d + len) {
                    q.push({r, d + len, v});
                }
                continue;
            }

            int nr = search(r + 1, c, len);
            if (nr == -1) continue;
            if (dis[v][0] > nr or dis[v][1] == nr and dis[v][1] > len) {
                q.push({nr, len, v});
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << vis[i];
    }
    puts("");
}

L LIS

二维平面每个整点 $(x, y)$ 都有连向 $(x + 1, y)$ 和 $(x, y + 1)$ 的两条无向路径。另外还有 $n$ 条特殊的无向路径连接 $(x_i, y_i)$ 和 $(x_i + 1, y_i + 1)$。

设 $f(x, y)$ 表示从 $(0, 0)$ 走到 $(x, y)$ 需要的最少路径数。给 $p$ 和 $q$，求 $\sum_{x = 0}^p\sum_{y=0}^{q}f(x,y)$

多组数据，$n \le 10^6$，$p, q \le 10^6$。

假如没有额外路径的话，$f(x, y) = x + y$

那么考虑上额外小径就是减去最多经过的额外小径数量

从贡献角度考虑，一个斜线 (x0, y0) -> (x0 + 1, y0 + 1) 会让 f(x > x0, y > y0) 这个矩形 -1。因此可以把所有斜线按 $x_i$ 为第一关键字升序，$y_i$ 为第二关键字降序排列。

这样走到 (x, y) 最多经过的斜线数量就等价于一个最长上升子序列的长度。

void solve() {
    int n = read();
    int p = read(), q = read();

    using pii = std::pair<int, int>;
    #define fi first 
    #define se second

    vector<pii> a(n);
    for (auto &[x, y] : a) {
        x = read(), y = read();
    }

    std::sort(a.begin(), a.end(), [](pii x, pii y) {
        return x.fi == y.fi ? x.se > y.se: x.fi < y.fi;
    });

    std::set<int> s;
    int ans = p * (p + 1) / 2 * (q + 1)
            + q * (q + 1) / 2 * (p + 1);

    int sum = 0, las = 0;
    for (auto [x, y] : a) {
        if (x >= p) break;
        if (y >= q) continue;

        if (las <= x) {
            ans -= (x - las + 1) * sum;
            las = x + 1;
        }

        if (s.empty() or y > *std::prev(s.end())) {
            s.insert(y);
            sum += q - y;
        } else {
            auto it = s.lower_bound(y);

            sum -= q - *it;
            sum += q - y;
            s.erase(it);
            s.insert(y);
        }
    }

    if (las <= p) {
        ans -= (p - las + 1) * sum;
    }

    cout << ans << '\n';
}