\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.0}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{orange}{\text{Hướng dẫn}}\)

• Mục tiêu: Với mỗi truy vấn

A) Chọn các giá trị \(x_i\) thỏa mãn

😎 Trong tất cả các cách chọn, chọn tổng bình phương lớn nhất có thể tạo ra

• Nhận xét 1: Ta có thể chọn \(x_i = a_i\ (\forall i = 1 \cdots.. n)\) trước

Sau đó với phần còn thừa lại, ta có thể thêm vào một số số \(x_i\)

Từ đây ta có tư tưởng trâu: Chọn các dãy \(y_i\) có tổng không vượt quá phần thừa. Tìm kết quả \(max(A) = max(\Sigma(x_i^2)) = max(\Sigma((a_i + y_i)^2)\)

Gọi phần thừa là \(p\). Thì độ phức tạp là : \(O(\overset{p}{\underset{k = 0}{\Sigma}}C^{n + k - 1}_{n})\)

• Nhận xét 2: \((x + 1)^2 > x\ \forall x \in \mathbb{N}\)

Vậy thì cách tối ưu nhất là mình không nên bỏ sót phần thừa. Hay chọn dãy \(x_i\) có tổng đúng bằng \(s\)

Gọi phần thừa là \(k\). Thì độ phức tạp là : \(O(C^{n + k - 1}_{n})\)

• Nhận xét 3: \((a + 1)^2 + (b - 1)^2 \geq a^2 + b^2 \ (\forall a, b \in \mathbb{N}, a \geq b)\)

Vậy giữa \(2\) số \(x_p > x_q\) mình nên giảm \(x_q\) xuống mức tối thiểu là \(a_q\) trong khi cộng \(x_p\) phần mình trừ từ \(x_q\)

Vậy giữa \(n\) số, ta sẽ bắt cặp đến khi nào không giảm thêm được nữa thì tổng hiện tại sẽ tối ưu. Cách này có vẻ \(O(n^2)\)

Để giảm độ phức tạp, ta chọn số max là \(x_p\). Thì ta cứ bắt cặp các \(x_q\) với \(x_p\) để đẩy \(x_p\) lên và giảm \(x_q\) xuống \(a_q\).

Trong khi đó \(x_p\) sẽ không giảm và các giá trị khác không tăng nên \(x_p\) luôn là giá trị lớn nhất. Nên độ phức tạp chỉ còn \(O(n)\)

• Nhận xét 4: Ta sẽ sử dụng cấu trúc dữ liệu để xử lí các truy vấn sau

A) Thêm phần tử \(x\) vào tập

😎 Xóa phần tử \(x\) khỏi tập

C) Sửa một phần tử \(x\) từ trong tập thành \(y\). (Thực hiện phép xóa \(x\) và thêm \(y\))

D) Tìm phần tử lớn nhất trong tập

E) Tính tổng lớn nhất hiện tại

Và cấu trúc tối ưu nhất là dạng cây, nên mỗi truy vấn ta chỉ cần mất \(O(log n)\) thời gian

\(\color{goldenrod}{\text{Tiếp cận}}\)

• Từ nhận xét 1, cách để duyệt toàn tập:

Với mỗi truy vấn, sau khi sửa giá trị \(a_i = x\), ta tính phần thừa \(p\) còn lại

Ta sinh ra các tập con \(n\) phần tử \(y_i\) với \((y_i \in \mathbb{N}, 0 \leq y_i \leq p, \Sigma(y_i) \leq p)\)

Từ đó ta có được tập \(X\) gồm các phần tử \(x_i = a_i + y_i\)

• Từ nhận xét 2, cách để duyệt trâu:

Các tập con \(y_i\) phải thỏa thêm điều kiện \(\Sigma(y_i) = p\)

• Từ nhận xét 3, cách để tính giá trị mỗi truy vấn

Nhận truy vấn và sửa lại giá trị \(a_i = x\)

Tạo được tập \(X\) gồm các phần tử \(x_i = a_i\)

Tìm phần tử lớn nhất trong mảng hiện tại là \(x_p\)

Tính phần thừa \(k = s - \Sigma(a_i)\)

Sửa \(x_p\) thành \(x_p + k\)

Tính tổng \(S = \Sigma(x_i^2)\) và xuất kết quả

• Từ nhận xét 4, ta có thể dùng cây đỏ đen ta có thể tính được các truy vấn trong

Với \(D\) là số phần tử phân biệt. Rõ ràng \(D = O(n)\)

A) Thêm trong \(O(log D)\)

😎 Xóa trong \(O(log D)\)

C) Sửa trong \(O(log D)\)

D) Tìm trong \(O(log D)\)

E) Duyệt qua và tính mất \(O(D)\)

• Nhận xét 5:

Mỗi lần muốn tính tổng ta phải duyệt lại qua toàn tập

Nhận thấy rằng khi sửa một phần tử (tức mỗi truy vấn) thì chỉ giá trị lớn nhất có thể bị thay đổi, phần còn lại giữ nguyên

Vậy khi ta thêm, xóa hoặc sửa phần tử ta có thể tính trực tiếp giá trị tổng hiện tại, lúc này trả lời truy vấn chỉ cần tìm phần tử lớn nhất và tính kết quả là xong

Vậy ta có thể xử lí truy vấn E) Tính trong \(O(log D)\)

Vậy mọi truy vấn có thể xử lí trong \(O(log D)\)

\(\color{green}{\text{Code tham khảo }}\): Giải trực tiếp, Cấu trúc dữ liệu đặc biệt

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(q \times log n)\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <iostream>
#include <map>

using namespace std;

struct Solver
{
    int limit;
    Solver (int limit) : limit(limit) {}

    map<int, int> M;
    int total = 0;
    long long result = 0;

    /// x^2
    long long square(int x)
    {
        return 1LL * x * x;
    }

    /// Add number to list
    void add(int x)
    {
        total += x;
        result += 1LL * x * x;
        ++M[x];
    }

    /// Remove number in list
    void rmv(int x)
    {
        total -= x;
        result -= 1LL * x * x;
        if (--M[x] == 0)
            M.erase(x);
    }

    /// Change number in list
    void modify(int x, int y)
    {
        rmv(x);
        add(y);
    }

    /// Maximum Sigma(x^2) satisfy (Sigma(x) = s) and (x >= ai)
    long long query()
    {
        int maxValue = M.rbegin() -> first;
        int remain = limit - total;
        return result + square(maxValue + remain) - square(maxValue);
        /// Modify maxValue -> maxValue + remain
    }
};

int main()
{
    int n, s;
    cin >> n >> s;

    int a[n + 1];
    Solver solver(s);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
        solver.add(a[i]);
    }

    int q;
    cin >> q;

    cout << solver.query() << '\n';
    while (q-->0)
    {
        int p, x;
        cin >> p >> x;

        solver.modify(a[p], x);
        a[p] = x;

        cout << solver.query() << '\n';
    }

    return 0;
}