Hiểu bài toán

Bài toán yêu cầu xử lý một mảng gồm N số nguyên và Q truy vấn. Có hai loại truy vấn:

1. Type 1: Cập nhật giá trị tại chỉ số i (theo mảng ban đầu) thành x, sau đó in ra tổng của toàn bộ mảng.
2. Type 2: Xoay mảng sang trái k đơn vị.

Mấu chốt của bài toán là các truy vấn Type 2 chỉ thay đổi 'góc nhìn' về mảng chứ không thay đổi thực tế các giá trị bên trong. Nếu ta lưu trữ mảng quá lớn (10^5 phần tử) và xoay nó trực tiếp (cần O(N)), ta sẽ gặp Time Limit Exceeded với Q lớn. Do đó, cần một cách tiếp cận hiệu quả hơn để ánh xạ chỉ số logic (theo yêu cầu của truy vấn) về chỉ số vật lý trong mảng đã lưu.

Các cách tiếp cận

Cách Mô phỏng xoay mảng trực tiếp

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

int main() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n);
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        sum += a[i];
    }

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int i; long long x;
            cin >> i >> x;
            // Truy vấn dùng chỉ số 1-based ban đầu
            // Vòng lặp xoay làm thay đổi chỉ số tương đối
            // Logic phức tạp để tìm vị trí thực tế sau nhiều lần xoay
            cout << sum << "\n"; 
        } else {
            int k;
            cin >> k;
            k %= n;
            // Xoay thực tế: O(N)
            // for (int i = 0; i < k; ++i) {
            //     long long first = a[0];
            //     for (int j = 0; j < n - 1; ++j) a[j] = a[j+1];
            //     a[n-1] = first;
            // }
        }
    }
    return 0;
}

• Time Complexity: O(N * Q) - Quá chậm
• Space Complexity: O(N)

Cách tiếp cận này cố gắng thực hiện xoay mảng trực tiếp sau mỗi truy vấn Type 2. Tuy nhiên, thao tác xoay mảng mất O(N) thời gian. Với N, Q lên đến 10^5, độ phức tạp tổng cộng có thể lên tới 10^10, dẫn đến quá thời gian. Đây là cách tiếp cận không khả thi nhưng là nền tảng để hiểu tại sao cần tối ưu hóa.

Cách Quản lý chỉ số bằng biến Shift (Optimal)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (fopen("dodep.inp", "r")) {
        freopen("dodep.inp", "r", stdin);
        freopen("dodep.out", "w", stdout);
    }

    ll n, q;
    cin >> n >> q;

    vector<ll> a(n + 1);
    ll sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    int shift = 0; // Biến đếm tổng số bước xoay

    while (q--) {
        ll type;
        cin >> type;

        if (type == 1) {
            ll i, x;
            cin >> i >> x;

            // Tính vị trí thực tế (vật lý) trong mảng
            // Công thức: (Chỉ số logic - 1 - tổng_xoay + N) % N + 1
            int pos = (i - 1 - shift + n) % n + 1;

            sum -= a[pos];
            a[pos] = x;
            sum += x;

            cout << sum << '\n';
        } else {
            ll k;
            cin >> k;
            // Cập nhật tổng số bước xoay
            // Dùng phép chia lấy dư để tránh tràn số
            shift = (shift + k) % n;
        }
    }
    return 0;
}

• Time Complexity: O(Q)
• Space Complexity: O(N)

Đây là phương pháp tối ưu.

1. Ta không xoay mảng thực tế.
2. Duy trì một biến shift để lưu tổng số bước xoay trái.
3. Khi nhận truy vấn Type 1 với chỉ số i (theo ban đầu), ta cần tìm vị trí của phần tử này trong mảng hiện tại.
   • Mảng ban đầu: A[1], A[2], ..., A[i], ..., A[n]
   • Sau khi xoay trái shift đơn vị: A[shift+1] lên đầu.
   • Để truy cập A[i] ban đầu, ta cần lùi lại shift bước trong mảng ban đầu.
   • Vị trí vật lý (0-based): (i - 1 - shift) % n.
   • Vị trí 1-based: ((i - 1 - shift) % n + n) % n + 1.
4. Cập nhật giá trị tại vị trí vật lý đó và tổng số tiền.

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán xoay mảng nhưng không thay đổi giá trị, chỉ thay đổi thứ tự truy cập. Do đó, không cần xoay mảng thực tế.
• Sử dụng biến đếm 'tổng số bước xoay' (shift) để ánh xạ chỉ số logic (ban đầu) về chỉ số vật lý (hiện tại).
• Công thức ánh xạ: vị trí = (i - 1 - shift + n) % n (với i là chỉ số 1-based ban đầu).

Lỗi thường gặp

• Sử dụng chỉ số âm trong phép chia lấy dư: Phải đảm bảo (a % n + n) % n hoặc dùng số học modulo số học (nếu ngôn ngữ hỗ trợ) để tránh lỗi.
• Quên cập nhật tổng số tiền (sum) mỗi khi thay đổi giá trị: Nếu chỉ thay đổi mảng mà không update sum, mỗi truy vấn Type 1 sẽ phải duyệt lại toàn bộ mảng để tính tổng, tăng độ phức tạp lên O(N).
• Lỗi chỉ số mảng (Off-by-one error): Bài dùng chỉ số 1-based để nhập vào (i), nhưng mảng C++ thường 0-based. Cần chuyển đổi đúng cách.