Tóm tắt đề bài

Cho dãy số nguyên \(a_1, a_2, \dots, a_n\) và một số nguyên \(s\). Ta cần tìm dãy số nguyên \(x_1, x_2, \dots, x_n\) sao cho:

• \(x_i \geq a_i\) với mọi \(i = 1 \dots n\).
• \(\sum_{i=1}^{n} x_i \leq s\).
• \(A = \sum_{i=1}^{n} x_i^2\) đạt giá trị lớn nhất.

Ngoài ra, có \(q\) truy vấn cập nhật giá trị \(a_i = x\). Sau mỗi truy vấn (và cả trạng thái ban đầu), hãy in ra giá trị lớn nhất của \(A\).

Phân tích

Nhận xét 1: Tổng của dãy \(x_i\)

Để tổng bình phương \(A\) lớn nhất, ta nên chọn các \(x_i\) sao cho tổng của chúng đạt giá trị lớn nhất có thể, tức là \(\sum x_i = s\). Điều này dựa trên tính chất \((x+1)^2 > x^2\) với \(x \geq 0\).

Nhận xét 2: Cách phân bổ giá trị để tối đa hóa tổng bình phương

Giả sử ta có hai số \(u, v\) và muốn tăng tổng của chúng thêm một lượng \(k > 0\). Ta nên cộng \(k\) vào số nào để tổng bình phương tăng nhiều nhất?
Xét hai trường hợp cộng vào \(u\) hoặc cộng vào \(v\) (giả sử \(u \geq v\)):

• Cộng vào \(u\): \((u+k)^2 + v^2 = u^2 + 2uk + k^2 + v^2\)
• Cộng vào \(v\): \(u^2 + (v+k)^2 = u^2 + v^2 + 2vk + k^2\)

Vì \(u \geq v\) nên \(2uk \geq 2vk\). Do đó, để tổng bình phương lớn nhất, ta nên dồn toàn bộ "phần dư" \(k = s - \sum a_i\) vào số có giá trị lớn nhất trong dãy.

Chiến thuật tối ưu

1. Gọi \(k = s - \sum_{i=1}^{n} a_i\) là phần dư còn lại sau khi đã gán \(x_i = a_i\).
2. Tìm giá trị lớn nhất trong dãy \(a\), gọi là \(a_{max}\).
3. Dãy \(x\) tối ưu sẽ là: một phần tử có giá trị \(a_{max} + k\), các phần tử còn lại giữ nguyên \(x_i = a_i\).
4. Tổng bình phương lớn nhất là:

Hướng giải quyết

Để xử lý các truy vấn cập nhật và tìm giá trị lớn nhất hiệu quả, ta cần quản lý các đại lượng sau:

• sumA: Tổng các phần tử \(\sum a_i\).
• sumA2: Tổng bình phương các phần tử \(\sum a_i^2\).
• maxA: Giá trị lớn nhất trong mảng \(a\).

Cấu trúc dữ liệu

• Sử dụng biến long long để lưu sumA và sumA2 nhằm tránh tràn số.
• Sử dụng std::multiset hoặc std::map trong C++ để duy trì danh sách các phần tử của mảng \(a\). Việc này giúp ta lấy ra phần tử lớn nhất (*set.rbegin()) và cập nhật phần tử trong \(O(\log n)\).

Các bước thực hiện

1. Khởi tạo: Tính sumA, sumA2 và cho các phần tử vào multiset.
2. Trả lời truy vấn:
   • Tính \(k = s - sumA\).
   • Lấy \(a_{max}\) từ multiset.
   • Kết quả là \(sumA2 - a_{max}^2 + (a_{max} + k)^2\).
3. Cập nhật \(a_i = x\):
   • Loại bỏ \(a_i\) cũ: sumA -= a_i, sumA2 -= a_i * a_i, xóa một bản sao của \(a_i\) trong multiset.
   • Thêm \(x\) mới: \(a_i = x\), sumA += x, sumA2 += x * x, thêm \(x\) vào multiset.
   • Lặp lại bước trả lời truy vấn.

Độ phức tạp

• Thời gian: \(O((n + q) \log n)\) do mỗi thao tác thêm/xóa/tìm max trên multiset tốn \(O(\log n)\).
• Bộ nhớ: \(O(n)\) để lưu trữ mảng và cấu trúc dữ liệu.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main() {
    // Tối ưu tốc độ nhập xuất
    ios::sync_with_stdio(0);
    cin.tie(NULL);

    int n;
    ll s;
    if (!(cin >> n >> s)) return 0;

    vector<ll> a(n + 1);
    ll sumA = 0;
    ll sumA2 = 0;
    multiset<ll> elements;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sumA += a[i];
        sumA2 += a[i] * a[i];
        elements.insert(a[i]);
    }

    int q;
    cin >> q;

    // Xử lý q + 1 lần (trạng thái đầu và q truy vấn)
    for (int z = 0; z <= q; z++) {
        if (z > 0) {
            int i;
            ll x;
            cin >> i >> x;

            // Cập nhật các tổng và multiset
            sumA -= a[i];
            sumA2 -= a[i] * a[i];
            elements.erase(elements.find(a[i]));

            a[i] = x;
            sumA += a[i];
            sumA2 += a[i] * a[i];
            elements.insert(a[i]);
        }

        // Tìm giá trị lớn nhất hiện tại
        ll maxA = *elements.rbegin();
        ll k = s - sumA;

        // Công thức: Tổng bình phương mới = (Tổng bình phương cũ - maxA^2) + (maxA + k)^2
        ll ans = sumA2 - maxA * maxA + (maxA + k) * (maxA + k);
        cout << ans << "\n";
    }

    return 0;
}