Hiểu bài toán

Bài toán yêu cầu mô phỏng trạng thái của n chiếc điều hòa. Ban đầu tất cả đều tắt (0). Có q thao tác, mỗi thao tác gồm hai số nguyên x, y (1 ≤ x ≤ y ≤ n), biểu thị việc bật/tắt tất cả các điều hòa từ vị trí x đến y (nghĩa là nếu đang tắt thì bật, đang bật thì tắt). Sau khi thực hiện xong q thao tác, in ra trạng thái cuối cùng của từng chiếc điều hòa (0 là tắt, 1 là bật).

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

Cách Brute Force (Mô phỏng trực tiếp)

#include <iostream>
using namespace std;
void AC() {
    int n,q; cin >> n >> q;
    int a[n+1];
    for(int i = 1; i <= n; i++) a[i] = 0;
    while(q--) {
        int x,y; cin >> x >> y;
        for(int i = x; i <= y; i++) {
            a[i] = 1 - a[i];
        }
    }
    for(int i = 1; i <= n; i++) cout << a[i] << ' ';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    AC();
    return 0;
}

• Time Complexity: O(n * q)
• Space Complexity: O(n)

Cách tiếp cận này sử dụng một mảng để lưu trạng thái của các điều hòa. Với mỗi thao tác (x, y), vòng lặp chạy từ x đến y để cập nhật trạng thái (toggled: 0 thành 1, 1 thành 0).

• Ưu điểm: Đơn giản, dễ hiểu, đúng với mô tả bài toán.
• Nhược điểm: Nếu n và q lớn (ví dụ n, q ~ 10^5), độ phức tạp thời gian O(n*q) sẽ quá chậm (khoảng 10^10 thao tác), dẫn đến TLE (Time Limit Exceeded).

Cách Difference Array (Xấp xỉ)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen("cau2.inp","r",stdin);
    // freopen("cau2.out","w",stdout);
    int n,k,a,b;
    cin>>n>>k;
    vector<int>diff(n+1,0);
    for(int i=0;i<k;++i){
        cin>>a>>b;
        diff[a-1]++; // Using 0-based indexing logic for diff array
        diff[b]--;
    }
    int cur=0;
    for(int i=0;i<n;++i){
        cur+=diff[i];
        cout<<cur%2<<" ";
    }
    return 0;
}

• Time Complexity: O(n + k)
• Space Complexity: O(n)

Thay vì cập nhật từng phần tử trong khoảng [x, y], ta sử dụng kỹ thuật Difference Array.

• Với mỗi truy vấn [x, y] (input 1-based), ta đánh dấu sự thay đổi:
  • Tăng diff[x-1] lên 1 (bắt đầu).
  • Giảm diff[y] đi 1 (kết thúc).
• Sau khi xử lý hết các truy vấn, ta duyệt mảng diff và tính tổng tiền tố (prefix sum). Biến cur lưu số lượng thao tác bao trùm lên vị trí hiện tại.
• Trạng thái cuối cùng của vị trí i là cur % 2 (vì mỗi thao tác là một lần lật).
• Đặt diff size n+1 để tránh tràn mảng khi b == n.
• Độ phức tạp: O(n + k) cho k truy vấn, rất nhanh.

Cách Prefix Sum (Tổng tiền tố)

#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> air_conditioners(n, 0);

    for (int i = 0; i < q; ++i) {
        int x, y;
        cin >> x >> y;
        // Adjust indices to be 0-based
        x--;
        y--;
        for (int j = x; j <= y; ++j) {
            air_conditioners[j] = 1 - air_conditioners[j];
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << air_conditioners[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

• Time Complexity: O(n * q)
• Space Complexity: O(n)

Đây là cách tiếp cận Brute Force (Solution 3).

• Tạo mảng air_conditioners.
• Với mỗi truy vấn [x, y], lặp từ x đến y để lật trạng thái.
• Rõ ràng là cách này chậm nhất và chỉ phù hợp với dữ liệu nhỏ.

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

Bài học kinh nghiệm

• Bài toán là bài toán cập nhật khoảng và truy vấn trạng thái cuối cùng. Kỹ thuật Difference Array (hoặc Prefix Sum) là tối ưu nhất cho các bài toán dạng 'cập nhật vùng, truy vấn tổng/số lần'.
• Việc lật trạng thái (0->1, 1->0) tương đương với việc cộng 1 modulo 2. Do đó, ta có thể đếm số lần mỗi vị trí được bao phủ bởi các truy vấn, sau đó lấy số đó chia 2 lấy dư.

Lỗi thường gặp

• Lỗi chỉ số mảng (Off-by-one error): Input là 1-based (từ 1 đến n), nhưng code C++ thường dùng 0-based. Cần chuyển đổi x-- trước khi dùng làm chỉ số, hoặc dùng diff array size n+1 và thao tác cẩn thận.
• Tràn số nguyên: Nếu dùng mảng int để lưu tổng tiền tố và số truy vấn lớn, có thể tràn số. Tuy nhiên, trong bài này chỉ cần chia 2 lấy dư nên giá trị lưu trữ không cần quá lớn, nhưng vẫn nên chú ý.