# 9A-9B 21/12
## Bài A
Cho dãy $A$ gồm $N$ số nguyên.
Làm việc sau $K$ lần:
- Xóa số đầu tiên
- Thêm 0 vào sau cùng của $A$
## Bài B
Thời gian được viết dưới dạng `hh-mm`: (giờ trước, ngày sau) trong đó giờ nằm trong đoạn $[0,23]$
Giờ "gây lú" là đảo một số kí tự vẫn đọc ra được một giờ đúng khác.
Tìm thời điểm gần nhất sau giờ hiện tại mà "gây lú"

### Cách làm:
Chạy trâu, tăng dần từng phút lên và kiểm tra

## Bài C
Mô phỏng lại Twidai (twitter). Có $Q$ sự kiện:
- A theo dõi B
- A bỏ theo dõi B
- Tại thời điểm đang hỏi, A và B có theo dõi lẫn nhau hay không?

Lúc đầu, không có ai theo dõi ai khác.
$N$ lớn ($10^9$), $Q$ đủ bé ($\le 2.10^5$)

### Hướng 1: Trâu $O(Q^2)$
Tại mỗi thời điểm được hỏi, ta sẽ duyệt ngược về các thời điểm trước đó để xem thử:
- Gần đây A (hoặc B) có bỏ theo dõi người còn lại không?
- A và B gần đây có theo dõi không?

(không ổn lắm vì a code bug, xem lại sau)

### Hướng 2:
Dùng Set của C++, có thể cài bằng cái khác (như Map)

## Bài D
Cho dãy $A$ độ dài $N$, có $Q$ thao tác, thuộc vào 3 loại sau:
1. Gán mọi phần tử $= x$
2. Tăng phần tử $A[i]$ lên $x$ đơn vị
3. Hỏi giá trị của số thứ $i$.

$N,Q \le 2.10^5$

### Trâu:
Đề bảo sao làm vậy, độ phức tạp $O(NQ)$
### Chuẩn:
Chỉ cần quan tâm những thao tác cộng (loại 2) mà nằm sau thao tác loại $1$ cuối cùng. Vì trước đó có thay đổi gì đi nữa thì gặp loại 1, cả mảng có cùng giá trị.
Để làm được như vậy thì tại mỗi vị trí, ta lưu lại danh sách các thao tác cộng vào nó (và cả thời điểm cộng). Khi gặp câu hỏi tại vị trí $i$ này thì xóa hết những phép cộng trước thao tác loại 1 cuối cùng.

### Hesll re-explains the solution:
**Nhận xét:** Mỗi lần xuất hiện truy vấn 1, toàn bộ các truy vấn còn lại **đều bị hủy bỏ**

Vì vậy, ta coi như ban đầu (và sau mỗi lần truy vấn 1), mọi thứ đều trống rỗng.
Mỗi truy vấn loại 2 sẽ thay đổi đi một phần tử, để nó có tăng giá trị, chứ không còn trống rỗng nữa.
Nhưng, với mỗi truy vấn loại 3, nếu phần tử được xét:
- Có giá trị $\Rightarrow$ in ra giá trị của phần tử + **giá trị mặc định**
- Trống rỗng $\Rightarrow$ giá trị **mặc định**

**Giá trị mặc định** này được thay đổi **ngay sau mỗi truy vấn 1**.

#### Thuật toán cho mỗi truy vấn:
- Nếu là loại 1: xóa toàn bộ truy vấn cũ (*), tương đương với đặt lại mảng $A$ toàn bộ bằng $0$. Đồng thời, mặc định `def = x`.
- Nếu là loại 2: `A[i] += x`
- Nếu là loại 3: `print(def + A[i])`

Để xóa toàn bộ truy vấn cũ, thay vì phải gán toàn bộ giá trị mảng $A$ bằng $0$, ta nhận thấy chỉ cần gán cho các phần tử đã bị thay đổi. Vì chỉ có $q$ lần thay đổi tổng cộng, nên độ phức tạp là $\mathcal{O}(q)$ thay vì là $\mathcal{O}(n\times q_1)$.

Vì vậy, tạo mảng lưu lại các vị trí đã bị thay đổi. Lhi cần xóa, ta duyệt lại các vị trí này, sau đó gán bằng 0, rồi ta xóa hết mảng này và làm lại từ đầu.

affect: vector<int> = {}
A: int[] = {0, 0, 0, 0, ...}
def: int = 0

với mỗi truy vấn (type, i, x):
    nếu type == 1:
        def = x;
        với mỗi vị trí i' trong affect
            A[i'] = 0;
        affect.clear();
    nếu type == 2:
        A[i] += x
        affect.push_back(i);
    nếu type == 3:
        in ra def + A[i]
    

## Bài E
Cho một bảng có $H$ hàng, $W$ cột, các giá trị trong bảng nằm trong khoảng từ $1 \rightarrow N$ $(1 \le H, W, N \le 300)$

Cho hai số $h, w$. Với mỗi hình chữ nhật có kích cỡ $h\times w$ có góc trái trên là $(i, j)$ $(1 \le i \le H - h + 1, 1 \le j \le W - w + 1)$, nếu xóa khỏi bảng toàn bộ các số trong hình chữ nhật này, thì phần còn lại **có bao nhiêu loại số khác nhau**.

### Solution
Đầu tiên, ta cần biết một số xuất hiện bao nhiêu lần trong bảng, điều này có dễ dàng tìm được bằng mảng cộng dồn hai chiều.

---

Tổng tiền tố 2 chiều. Cần $N$ bảng như vậy cho mỗi giá trị khác nhau. Cụ thể hơn, cần tính `cnt[i][x][y]`: có bao nhiêu giá trị $i$ trong hình chữ nhật có góc trái trên là $(1,1)$, góc phải dưới là $(x,y)$.

---

Mỗi lần đếm xem số lượng số $i$ trong bảng từ $(x_1, y_1)$ tới $(x_2, y_2)$, ta lấy `cnt[i][x2][y2] - cnt[i][x2][y1 - 1] - cnt[i][x1 - 1][y2] + cnt[i][x1 - 1][y1 - 1]`.

Thuật toán của bài này là: đầu tiên đếm xem có bao nhiêu số từ $1 \rightarrow N$ trong bảng và lưu lại. Sau đó, duyệt từng bảng $h\times w$, tính lại số lượng các số từ $1 \rightarrow N$ rồi trừ ra, lấy từng hiệu đem xét để tính đáp án cho mỗi hình chữ nhật đó.

## Bài F
Quy hoạch động bitmask