Hướng dẫn cho Kiến trúc sư và con đường


Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: SPyofgame


Spoiler Alert


Hint 1

  • Trâu từng đoạn một

Với mỗi truy vấn ta tính \(sum_{l..r} = \Sigma(l \leq i \leq r)\{a_i\}\)

Độ dài đoạn là \(len = r - l\)

Kết quả là trung bình cộng đoạn này: \(\frac{sum}{len}\)


Hint 2

  • Sử dụng mảng cộng dồn

Với \(a[i]_{sau} = \Sigma(1 \leq j \leq i)\{a[j]_{trước}\}\)

Ta dễ dàng tính \(sum_{l..r}\)

\(= \Sigma(l \leq i \leq r)\{a[i]_{trước}\} = \Sigma(1 \leq i \leq r)\{a[i]_{trước}\} - \Sigma(1 \leq i \leq l - 1)\{a[i]_{trước}\} = a[r]_{sau} - a[l - 1]_{sau}\)


Reference AC code | \(O(n)\) time | \(O(1)\) query | \(O(n)\) auxiliary space | Query-problem, Prefix-sum

C++
int main()
{
    /// Input
    int n = readInt();
    vector<ll> a(n + 1, 0); /// a[0] = 0
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];      /// a[i] truoc
        a[i] += a[i - 1]; /// a[i] sau
    }

    /// Solve
    for (int q = readInt(); q--; )
    {
        int l, r;
        cin >> l >> r;
        cout << setprecision(6) << fixed << double(a[r - 1] - a[l - 1]) / (r - l) << '\n';
    }
    return 0;
}


Bình luận

Không có bình luận nào.