# Solution bài 2 Round 3 - SHOPPING

## Tóm tắt
Cho dãy nguyên dương $n$ phần tử, $q$ truy vấn gồm $l, u, v, k$. Đếm số lượng vị trí $r$ sao cho $$ \sum_{i = l, a_i \in [u, v]}^r a_i \leq k $$.

## Subtask 1: $k$ bằng nhau, $u = 1, v = 10^9$
Do $u \leq a_i \leq v$, nên ta có thể phát biểu bài toán thành đếm số lượng vị trí $r$ sao cho $\sum_{i = l}^r a_i \leq k$.

Do $k$ bằng nhau với mọi truy vấn, ta tiến hành sắp xếp các truy vấn theo $l$, sau đó tìm $f(l)$ là vị trí $r$ phải nhất sao cho $sum[l, r] \leq k$. Ta có thể dễ dàng tìm bằng kĩ thuật hai con trỏ. Đáp án cho truy vấn sẽ là $f(l)-l+1$.

Độ phức tạp: $O(n + q + q\log q)$ với $q \log q$ là chi phí sắp xếp truy vấn.

Code tham khảo: [SHOPPING 1st subtask](https://ideone.com/HVU9LD)

## Subtask 2: $a_i \leq 500$

Do $a_i \leq 500$, ta tiến hành tính $sum[v][r] = \sum_{i = 1, a_i \leq v}^r a_i$. Ta có thể tính trong $O(n \cdot a_i)$ theo công thức sau
$$
sum[v][r] = \begin{cases}
sum[v][r-1] + a_r & \text{nếu } a_r \leq v\\
sum[v][r-1] & \text{ngược lại}
\end{cases}
$$

Do khi $r$ càng lớn thì tổng cần tìm càng lớn, ta có thể trả lời truy vấn bằng cách chặt nhị phân để tìm $f(l)$. Với vị trí $r$, ta có thể tính tổng $g(l, r, u, v)$ trong $O(1)$ sau đó so sánh với $k$:
$$
g(l, r, u, v) = (sum[v][r] - sum[v][l-1]) - (sum[u-1][r] - sum[u-1][l-1])
$$

Độ phức tạp: $O(n \cdot a_i + q)$

Code tham khảo: [SHOPPING 2nd subtask](https://ideone.com/44RXp7)

## Subtask 3: $v-u \leq 5$
Áp dụng ý tưởng chặt nhị phân và tính tổng theo giá trị của subtask 2, ta rời rạc hóa giá trị các phần tử của $a_i$ cùng với các giá trị $u, v$ trong các truy vấn. Dễ thấy có tối đa $n+2q$ giá trị phân biệt. Ta chia các phần tử vào các nhóm, mỗi nhóm gồm vị trí các phần tử có cùng giá trị. Từ đó ta có thể tính tổng $g(l, r, u, v)$ bằng cách đếm số phần tử trong đoạn $[l, r]$ của từng nhóm chứa các phần tử cùng giá trị $x \in [u, v]$.

Độ phức tạp bộ nhớ: Do mỗi nhóm chỉ chứa các phần tử có cùng giá trị mà nhóm đó đảm nhận nên ta có độ phức tạp bộ nhớ là $O(n + 2q)$.

Độ phức tạp thời gian: $O(n \log n + q \cdot \log n \cdot \max(v-u)) \approx O(n \log n + q \log n)$

Code tham khảo: [SHOPPING 3rd subtask](https://ideone.com/GSJ8eq)

## Subtask 4: $u = 1$
Áp dụng ý tưởng xử lí offline ở subtask 1 và chặt nhị phân ở subtask 2, trong subtask này, ta sắp xếp các truy vấn theo $v_i$ không giảm. Sau đó, ta duyệt truy vấn theo thứ tự đã sắp xếp, đồng thời duy trì một cây Fenwick lưu tổng các phần tử có giá trị không vượt quá $v_i$ theo vị trí các phần tử đó. Sau đó ta chặt nhị phân để tìm $f(l)$ bằng cách tính tổng $g(l, r, u, v)$ trên cây Fenwick để so sánh với $k$.

Để duy trì cây Fenwick, ta có thể sắp xếp các phần tử trong $a$ theo thứ tự không giảm, sau đó dùng kĩ thuật hai con trỏ để cập nhật lên cây các phần tử $a_x \leq v_i$.

Độ phức tạp: ta duy trì cây Fenwick trong toàn bộ bài toán mất $O(n\log n)$, trả lời mỗi truy vấn trong $O(\log^2 n)$. Như vậy, độ phức tạp là $O(n\log n + q \log^2 n)$.

Code tham khảo: [SHOPPING 4th subtask](https://ideone.com/huSzuL)
## Subtask 5: ràng buộc gốc

### Lời giải tác giả: Chặt nhị phân song song
Xuất phát từ lời giải của subtask 4, ở subtask này ta cần thêm một cận $u$ cho giá trị của các phần tử khi tính tổng.

#### Nhận xét 1
Ở mỗi truy vấn, ta cần thông tin từ $2$ cây Fenwick: cây $F_1$ chứa các phần tử $\leq v$ (giống subtask 4), cây $F_2$ chứa các phần tử $< u$. Từ đó, trong mỗi lượt chặt nhị phân, ta có thể tính $g(l, r, u, v)$ bằng tổng đoạn $[l, r]$ trong cây $F_1$ trừ đi tổng đoạn $[l, r]$ trong cây $F_2$.

#### Nhận xét 2
Ở mỗi truy vấn, ta đều cần tìm cách dựng hai cây Fenwick, sau đó chặt nhị phân rồi dùng hai cây này để so sánh với $k$. Nếu dùng hai con trỏ để duy trì hai cây, độ phức tạp thuật toán có thể lên tới $O(n^2)$. Đồng thời, ta nhận thấy thao tác cập nhật các phần tử từ $1$ đến vị trí $x$ nào đó cho cây Fenwick sẽ được thực hiện lặp lại nhiều lần qua các truy vấn.

#### Thuật toán
Từ hai nhận xét trên, ta cân nhắc kĩ thuật chặt nhị phân song song. Ở mỗi lượt chặt nhị phân, ta có danh sách các truy vấn cần giải quyết có dạng $(l, r, u, v)$: *tính tổng các phần tử có giá trị thuộc $[u, v]$ nằm trong đoạn vị trí $[l, r]$*. Ta tiến hành chia mỗi truy vấn này thành $2$ thao tác có dạng:
- $(v, l, r, 1)$: Cộng tổng các phần tử nhỏ hơn hoặc bằng $v$ vào tổng cần tính của truy vấn.
- $(u-1, l, r, -1)$: Trừ tổng các phần tử nhỏ hơn $u$ vào tổng cần tính của truy vấn.

Đồng thời, ta thêm thao tác $(i, a_i)$: cập nhật phần tử $a_i$ vào cây Fenwick.

Sau đó, ta sắp xếp các thao tác này theo giá trị của phần tử và tính tổng cho $q$ truy vấn với độ phức tạp chỉ là $O((q+n)\log n)$.

Độ phức tạp:
- Với việc chặt nhị phân song song, ta có tối đa $O(\log n)$ lượt chặt nhị phân. Do đó độ phức tạp thời gian của thuật toán là $O((q+n) \log^2 n)$.
- Do ta chỉ lưu danh sách các thao tác và một cây Fenwick duy nhất cho kĩ thuật chặt nhị phân song song, nên độ phức tạp bộ nhớ chỉ là $O(q+n)$.

Code tham khảo: [SHOPPING Parallel Binary Search](https://ideone.com/otUSEz)

### Lời giải đóng góp: Thuật toán MO
>Cảm ơn bạn Trần Hoàng Sơn đã đóng góp lời giải này.

Dựa trên ý tưởng của subtask 1. Nếu chúng ta kiểm soát được các phần tử $a_i$ trong đoạn $[u, v]$ thì hoàn toàn có thể tính được kết quả của từng truy vấn bằng nhiều phương pháp khác nhau như chặt nhị phân, Segment tree…

Khi $u$ và $v$ thay đổi thì hiển nhiên các phần tử chúng ta kiểm soát cũng thay đổi, và để thuận tiện trong việc kiểm soát các phần tử liên tục, chúng ta có thể sử dụng MO’s algorithm.

Trước tiên, dựa vào ý tưởng của subtask 3, chúng ta sẽ rời rạc hóa tất cả các giá trị $u, v$ và từng phần tử $a_i$. Lúc này với từng truy vấn chúng ta có thể dễ dàng kiểm soát các giá trị $a_i$ trong khoảng. Tuy nhiên sẽ có trường hợp nhiều phần tử $a_i$ cùng nằm tại $1$ điểm và khi chạy các truy vấn sẽ đi qua điểm đấy nhiều lần dẫn đến việc gia tăng độ phức tạp. Giải pháp cho vấn đề này là chúng ta sẽ tách các phần tử đấy ra thành các giá trị khác nhau sao cho vẫn thỏa mãn điều kiện nằm trong đoạn $[u, v]$. Sau khi hoàn thành bước này, độ phức tạp vẫn được đảm bảo là $O(\sqrt{n})$.

Bước tiếp theo, khi đã kiểm soát được các phần tử trong đoạn $[u, v]$, chúng ta sẽ tìm cách để trả lời cho từng truy vấn. Với việc thêm và xóa các phần tử liên tục, không khó để áp dụng cấu trúc Segment tree. Tuy nhiên khi dùng cấu trúc dữ liệu này thì độ phức tạp sẽ lên tới $O(n \sqrt{n} \log{n})$ (độ phức tạp quá lớn).

Một giải pháp khác chính là sử dụng mảng lưu tổng cho từng block. Khi chúng ta đã có được tổng cho từng block thì chỉ cần chạy qua từng block cho đến khi nào mà tổng hiện tại $> k$ thì chúng ta sẽ đi hẳn vào các phần tử trong block đấy rồi lại tiếp tục chạy đến khi nào tổng hiện tại $> k$ thì sẽ trả lời được truy vấn hiện tại. Độ phức tạp của giải pháp này là *số block + số phần tử trong 1 block*. Để thuận tiện chúng ta sẽ cố định số phần tử trong block là $\sqrt{n}$.

Tổng độ phức tạp :
- MO mất $O((n + 2q) \sqrt{n + 2q})$.
- Thêm, xóa các truy vấn trong $O(1)$.
- Trả lời từng truy vấn trong $O(\sqrt{n})$.
$\Rightarrow$ Tổng độ phức tạp : $O((n + 2q) \sqrt{n + 2q})$.

Code mẫu: [SHOPPING MO](https://ideone.com/JNGi7F).