---
tags: Programming Contest
---

# ACL Beginner Contest 題解

[題目連結](https://atcoder.jp/contests/abl/tasks)

## 心得

比賽中解出四題，rating +72 \(๑╹◡╹๑)ﾉ♬

## A. Repeat ACL

K = int(input())
print('ACL' * K)

## B. Integer Preference

檢查區間端點在不在另一個區間之中，反向也要檢查一遍。

A, B, C, D = map(int, input().split())

if C <= A <= D or C <= B <= D or A <= C <= B or A <= D <= B:
    print('Yes')
else:
    print('No')

## C. Connect Cities

假設整個 graph 會有 g 個彼此不連通的單元，在他們之間建 g - 1 條邊即可使他們連通。g = 1 時，即整個 graph 是連通的，那答案是 0。這題我嘗試用 ACL 的 Disjoint Set 來解。

#include <algorithm>
#include <atcoder/dsu>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    auto comps = atcoder::dsu(N);
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        comps.merge(u, v);
    }

    int n_comp = comps.groups().size();
    int ans = ((n_comp == 1) ? 0 : n_comp - 1);
    cout << ans << endl;

    return 0;
}

## D. Flat Subsequence

這題讓人想到 LIS，所以我就回憶了一下 LIS $O(nlgn)$ 的解法，改改看。

讓我們從左至右迭代 `A`，同時維護 `dp` 陣列：

dp[i] = max length of B where B[-1] = i

這個 dp 陣列的大小即為所有可能的數字`3e5 + 1`，陣列的初使值全為 0。

在 `A[i]` 時，我們可能從哪些數字轉移過來呢？所有位於區間 `[A[i] - K, A[i] + K]` 的數字都可以，於是寫出轉移方程：

dp[A[i]] = max([dp[j] for j in range(A[i] - k, A[j] + k + 1)]) + 1

會發現這樣的 dp 要 $O(NK)$ 才能算完。但觀察可以發現，我們的轉移方程是從 `dp[A[i] - K ... A[i] + K]` 中取最大值出來，再加 1。如果我們**用線段樹來存 dp**，這個操作就可以從 $O(M)$ 變成 $O(lgM)$，也因此整體時間是 $O(NlgM)$，$M$ 是數字的值域大小。

實作上小心 `A[i] - K` 小於 `0` 與 `A[i] + K` 大於等於 `N` 的情況，我因為這個 RE 了一次。
以下給出使用 ACL 的程式碼：

#include <algorithm>
#include <atcoder/segtree>
#include <iostream>
#include <vector>

using namespace std;

int op(int a, int b) { return max(a, b); }
int default_data() { return 0; }
using SegTree = atcoder::segtree<int, op, default_data>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }

    // dp[i] = the max length of B where B[-1] = i
    const int M = 300000 + 10;
    auto dp = SegTree(M);
    dp.set(A[0], 1);
    for (int i = 1; i < N; i++) {
        auto lb = max(A[i] - K, 0);
        auto ub = min(A[i] + K + 1, M);
        dp.set(A[i], dp.prod(lb, ub) + 1);
    }
    cout << dp.prod(0, M) << endl;

    return 0;
}

## E. Replace Digits

比賽中早早想到是 LazySegTree 但遲遲實作不出來 (｡ŏ﹏ŏ)。
今天藉由研究 kort0n 的[程式碼](https://atcoder.jp/contests/abl/submissions/17033157)，終於搞懂要怎麼使用 ACL 解決這題了，感謝大大。

存 `54873126` 的線段樹：


可以想到將 N 位數分解成 N 個值的和，然後用線段樹存，讓線段樹的 root 就是題目所求，如圖 1。

但只存值無法讓我們處理 query。當我們想將區間 `[l, r]` 都改成數字 `d` 時，我們不知道 `[l, r]` 對應的是哪些位數（如果自己刻線段樹的話應該可以，但 ACL 的 interface 不行），所以我們在每個節點除了 `value` 外，另外存一個 `base`，代表該節點 **對應的那些位數的和**，如圖 2。

這樣要將 `[l, r]` 都改成 `d` 時，區間對應的那些節點 `node` 的新 `value` 就會是 `d * node.base`。

實作上要小心 ACL 的 `apply_lazy`, `push_lazy` 在 `lazy` 是預設值時仍然會被呼叫，這跟我的直覺不同，被卡了好久。我們得在函式中判別這種情況。不能讓預設的 lazy （此題是 0）把該點與其子樹的結果給覆蓋掉。

#include <atcoder/lazysegtree>
#include <atcoder/modint>
#include <iostream>
#include <vector>
using namespace std;

using mint = atcoder::modint998244353;

struct S {
    mint value;
    mint base;
};
using F = int;

S op(S a, S b) { return {a.value + b.value, a.base + b.base}; }
S default_data() { return {0, 0}; }
S apply_lazy(F lazy, S data) {
    if (lazy == 0) {
        return data;
    }
    return {lazy * data.base, data.base};
}
F push_lazy(F root, F child) {
    if (root == 0) {
        return child;
    }
    return root;
}
F default_lazy() { return 0; }

using SegTree = atcoder::lazy_segtree<S, op, default_data, F, apply_lazy,
                                      push_lazy, default_lazy>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    auto leaves = vector<S>(N);
    mint base = 1;
    for (int i = 0; i < N; i++) {
        leaves[i] = {base, base};
        base = base * 10;
    }
    auto tree = SegTree(leaves);

    while (Q--) {
        int l, r, d;
        cin >> l >> r >> d;
        l--;
        r--;
        tree.apply(N - 1 - r, N - l, d);
        cout << tree.all_prod().value.val() << "\n";
    }

    return 0;
}

:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::