---
tags: Programming Contest
---

# AtCoder Beginner Contest 174 題解

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

## 心得

解五題，排 1387

## A, B

略

## C. Repsept

序列的數字可能非常大，該怎麼高速地判定某大數是不是 K 的倍數呢？Horner's Rule！這個技巧真常出現。

同時序列的每一項是其前一項乘 10 再加 7，這就可以跟 Horner's Rule 結合在一起，所以我們可以高速的迭代序列的每項，同時判斷各項是不是 K 的倍數。問題是該最多該迭代幾項，都沒找到就判定不存在？比賽時我直接猜是 K 項，沒仔細思考，然後就過了。

賽後同學分析：因為是對 K 取餘數，餘數的可能為 [0, K - 1] ，共 K 個，所以取餘數超過 K 次結果必重覆，形成循環。當有循環時，還沒找到倍數即無解，所以檢查 K 項就能知道有沒有解。

K = int(input())

def solve():
    val = 0
    for i in range(1, K + 1):
        val = val * 10 + 7
        val = val % K
        if val == 0:
            return i
    
    return -1

print(solve())

## D. Alter Altar

畫出幾個 testcase 研究研究，發現二個結論：

1. 最終字串必形成 `RRR...WWWW` 的型式。
2. 沒必要「改顏色」，只使用「交換」所需的操作數就是最小的。

第二點是因為「交換」一次將兩個位置處理好，「改顏色」一次只能處理好一個位置。

於是我的方法很簡單：將最終字串建出來跟原字串比一下，看有幾個位置需要處理，該值除上 2 即為答案。

N = int(input())
C = input()
T = 'R' * C.count('R') + 'W' * C.count('W')
ans = sum([1 for a, b in zip(C, T) if a != b]) // 2
print(ans)

## E. Logs

最大值最小化，二分搜！對應的 check 為：看看是不是只需 K 刀或更少就能將 logs 分割成最長長度為 l，換一個講法是：將每個 log，都盡量切成最長的長度 l，看最後的總刀數是不是 <= K。這可以在 $O(N)$ 時間算出，因為在給定某個 log 的長度為 $a$ 時，將之分解成每塊最長長度都是 $l$ 所需的刀數為 $\lceil \frac{a}{l} \rceil - 1$，可以 $O(1)$ 得到。$\lceil \frac{a}{l} \rceil$ 代表的是最後有幾塊，減上 1 就是所需刀數。

from math import ceil

N, K = map(int, input().split())
A = list(map(int, input().split()))

def check(l):
    cnt = sum(ceil(a / l) - 1 for a in A)
    return cnt <= K

lb, ub = 0, max(A)
for _ in range(50):
    mid = (lb + ub) / 2
    if check(mid):
        ub = mid
    else:
        lb = mid
print(ceil(ub))

## F. Range Set Query

這題好像是經典題，不過我沒解過。這題因為 $c_i$ 很大，我們無法將之塞進位元，然後用一個線段樹解決。

給定一個序列 `A`，我們建構一個序列 `B`，長度與 `A` 相同，且滿足一個特性：對於 `A` 中的每種數字 `d` 與 `d` 所在的那些位置，只有最右邊那個位置 `p`, `B[p] = 1`，`B` 的其他位置都是 `0`，以下給出一些例子：

序列 `A = [1, 2, 3]`，對應 `B = [1, 1, 1]`。
序列 `A = [1, 2, 1]`，對應 `B = [0, 1, 1]`。
序列 `A = [1, 1, 1]`，對應 `B = [0, 0, 1]`。

這樣的序列 B 讓我們有一個很好的特性，當我們想知道 A 有多少個不同值時，只要加總 B 就能得到結果，事實上這個結論對所有 A 的後綴都成立：**想知道 `A[i:]` 有多少不同值，答案為 `sum(B[i:])`**。

利用這個特性，對於題目所給的 C，我們可以設計出這樣的演算法：

for i in range(len(C)):
    求出 C[:i] 所對應的 B
    若存在 query 的右界是 i, 即 (l, i)，那這個 query 的答案是 sum(B[l:])

顯然 `C[:i - 1]` 對應的 `B` 與 `C[:i]` 對應的 `B` 是非常像的。我們只需另一個陣列 `last` 記錄每種數字最後一次出現的地方，這樣當我們從 `i - 1` 迭代到 `i`，只需將 `B` 中位於 `last[C[i]]` 的那個 `1` 移至位置 `i`，就能高速地得到新的 `B`。另外為了高速的查詢 `B` 的後綴和，我們使用 SegTree 或 BIT 來存 `B`。

seg = SegTree(len(N), 0) # B
last = defaultdict(lambda: -1) # -1 = not appeared yet

for i, c in enumerate(C):
    # Compute B corresponding to C[:i] and update last
    if last[c] != -1:
        seg.increment(last[c], -1)
    seg.increment(i, +1)
    last[c] = i
    
    # Compute ans if there are queries ending at i
    for query in queries_end_at_i:
        query.ans = seg.sum([query.l, query.r])

最後給出使用 BIT 的 C++ AC Code:

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using namespace std;

typedef tuple<int, int, int> t3i;

// API use 0-based index while internal implementation use 1-based index
template <class T>
struct BIT {
    int NN;
    vector<T> data;

    BIT(int N, T default_value) {
        NN = N;
        data = vector<T>(NN + 1, default_value);
    }

    void add_at(int idx, T val) {
        for (int i = idx + 1; i <= NN; i += (i & (-i))) {
            data[i] += val;
        }
    }

    T sum_to(int idx) const { // [0, idx]
        T res = 0;
        for (int i = idx + 1; i >= 1; i -= (i & (-i))) {
            res += data[i];
        }
        return res;
    }

    T sum_in(int l, int r) const { // [l, r]
        return sum_to(r) - sum_to(l - 1);
    }
};


template <class T>
ostream & operator << (ostream &out, const BIT<T> &bit) {
    out << "BIT(NN=" << bit.NN << ", ";
    out << "[ ";
    for (int i = 0; i < bit.NN; i++) {
        out << bit.sum_in(i, i) << " ";
    }
    out << "])";
    return out;
}


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

    int N, Q;
    cin >> N >> Q;
    
    auto C = vector<int>(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> C[i];
    }

    auto queries = vector<vector<t3i>>(N, vector<t3i>());
    for (int i = 0; i < Q; i++) {
        int l, r; 
        cin >> l >> r;
        l--; r--;
        queries[r].push_back({i, l, r});
    }

    auto ans = vector<int>(Q, -1);
    auto V = *max_element(C.begin(), C.end());
    auto last = vector<int>(V + 1, -1);
    
    auto bit = BIT<int>(N, 0);
    for (int i = 0; i < N; i++) {
        if (last[C[i]] != -1) {
            bit.add_at(last[C[i]], -1);
        }
        bit.add_at(i, +1);
        last[C[i]] = i;

        for (auto&& [id, l, r]: queries[i]) {
            ans[id] = bit.sum_in(l, r);
        }
    }

    for (auto x : ans) {
        cout << x << endl;
    }

    return 0;
}

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