# Note

- Bài 6 là bài heuristic (lần đầu xuất hiện trên VOI) nên mình sẽ không viết solution cho bài này (và mình cũng không có hứng thú với bài này lắm).
- Các bài tập từ bài 1 đến bài 5 đều có time limit là 1s và memory limit là 1024MB.
- Tham khảo từ: https://s.vnoi.info/LIVESTREAM-VOI-2026
- Cảm ơn anh Hoàng Dương (Trường THPT chuyên Nguyễn Huệ, Hà Nội) đã hỗ trợ em trong việc hoàn thành solution.

## Bài 1: Dãy đèn (LIGHT)

### Tóm tắt đề bài

Cho dãy đèn gồm $N$ bóng đèn, bóng đèn thứ $i$ có trạng thái là $S_i$ ($S_i=0,1,2$ tương ứng với trạng thái tắt, vàng hoặc đỏ). Với mỗi bóng đèn, có hai cách để thay đổi trạng thái bóng đèn như sau:
- **Cách 1:** Nếu trạng thái hiện tại là $x$, nó sẽ biến đổi thành trạng thái $(x+1)\ mod\ 3\ (0\rightarrow 1\rightarrow 2\rightarrow 0)$.
- **Cách 2:** Nếu trạng thái hiện tại là $x$, nó sẽ biến đổi thành trạng thái $(x-1)\ mod\ 3\ (0\rightarrow 2\rightarrow 1\rightarrow 0)$.

Bạn cần giải quyết $Q$ yêu cầu khảo sát, với yêu cầu khảo sát thứ $j$:
- Kiểm tra xem có thể thay đổi trạng thái tất cả bóng đèn từ $L_j$ đến $R_j$ về trạng thái tắt ($S=0$) hay không. Nếu có hãy in ra số thao tác ít nhất có thể để đưa các bóng đèn về trạng thái tắt, nếu không hãy in ra $-1$.
- Mỗi thao tác được phép chọn $X+Y$ bóng đèn phân biệt từ $L_j$ đến $R_j$, trong đó chọn $X$ bóng đèn để thay đổi trạng thái theo cách 1 và $Y$ bóng đèn còn lại biến đổi theo cách 2.

**Lưu ý:**
- Các yêu cầu khảo sát là độc lập, nghĩa là mỗi yêu cầu đều được xử lý trên trạng thái ban đầu của dãy đèn.
- $X$ và $Y$ là cố định cho tất cả $Q$ yêu cầu.

### Giới hạn và subtask
- $0<X+Y\le 5$
- $X+Y\le N\le 666$
- $1\le Q\le 10^5$
- $S_i\in \{0,1,2\}$ với mọi $i$ từ $1$ đến $N$
- $1\le L_j\le R_j\le N$ với mọi $j$ từ $1$ đến $Q$
- $R_j-L_j+1\ge X+Y$ với mọi $j$ từ $1$ đến $Q$

| Subtask | Điểm | Giới hạn |
|---------|--------|----------|
|1 |$30\%$ |$X=Y=1;N\le 10;Q=1$|
|2 |$20\%$ |$X=Y=1;Q=1$|
|3 |$34\%$ |$Q\le 5$|
|4 |$16\%$ |Không có ràng buộc gì thêm|

### Subtask 1: $X=Y=1;N\le 10;Q=1$

Với giới hạn $N$ rất nhỏ, và mỗi bóng đèn chỉ có $3$ trạng thái khác nhau nên ta có thể sinh hết mọi state lưu trạng thái của $N$ bóng đèn có thể xảy ra.

Ta sẽ áp dụng thuật toán BFS để giải quyết subtask này. Coi trạng thái của các bóng đèn trong yêu cầu khảo sát là state xuất phát và cần tìm số bước tối thiểu để đạt được state $\{0,0,0,\dots\}$.

Vì $X=Y=1$, với mỗi state ta chỉ cần for trâu để chọn hai bóng đèn sẽ thay đổi trạng thái trong state chuyển cần xét. Có $N\times (N-1)$ state chuyển khác nhau với mỗi state tương ứng.

Nhận xét độ phức tạp:
- Coi số lượng state là số đỉnh ($n$) và tổng số state chuyển với mỗi state là số cạnh của đồ thị ($m$). Độ phức tạp cho thuật toán BFS sẽ là $O(n+m)$.
- Có $3^N$ state khác nhau có thể tồn tại nên $n=3^N$, và với mỗi state có $N\times (N-1)$ state chuyển khác nhau nên $m=3^N\times N\times (N-1)$.

**Độ phức tạp:** $O\left(3^N+3^N\times N\times (N-1)\right)=O\left(3^N\times N^2\right)$.

**Lưu ý:** Nếu $Q>1$, ta vẫn có thể giải quyết được. Ta sẽ coi trạng thái $\{0,0,0,\dots\}$ là state xuất phát và BFS tới tất cả các state có thể xảy ra. Tuy nhiên, ta cần phải đảo ngược cách thay đổi trạng thái bóng đèn (**Cách 1** $\rightarrow$ **Cách 2** và ngược lại do hai cách thay đổi trạng thái này ngược nhau, hay đơn giản hơn là đổi giá trị của $X$ và $Y$ cho nhau).

### Subtask 2: $X=Y=1;Q=1$

Với $N$ lớn, ta không thể lưu hết mọi state có thể xảy ra, nên ý tưởng subtask 1 sẽ không thể thực hiện được nữa.

Vì giới hạn đặc biệt của subtask này ($X=Y=1$) nên ta có một nhận xét như sau:
- Gọi $sum=\left(\sum S_i\right)\ mod\ 3$. Khi thay đổi trạng thái của bóng đèn theo cách 1, $sum'=(sum+1)\ mod\ 3$, và theo cách 2 thì $sum'=(sum-1)\ mod\ 3$.
- Như vậy sau một thao tác, $sum'=(sum+1-1)\ mod\ 3=sum\ mod\ 3$. Hay nói cách khác, giá trị $sum$ trong quá trình thực hiện thao tác **luôn không đổi**.
- Nếu $sum\ne 0$ thì ta có thể suy ra ngay đáp án là $-1$.

Trong trường hợp ngược lại, ta biết là luôn tồn tại phương án để đưa các bóng đèn về trạng thái tắt. Gọi $a,b,c$ là số lượng bóng đèn có trạng thái $0,1,2$.

Ta có: $sum=(b+2c)\ mod\ 3=0 \leftrightarrow b\ mod\ 3=c\ mod\ 3$.

Tới đây thì ta có chiến thuật tham lam như sau:
- Các bóng đèn tắt ta hoàn toàn có thể bỏ qua.
- Trong trường hợp còn tồn tại ít nhất một bóng đèn ở trạng thái $1$ và $2$, ta sẽ thực hiện thao tác trên cả hai bóng đèn đó để đưa cả hai về trạng thái tắt. Cách làm này mất $1$ thao tác.
- Trong trường hợp các bóng đèn bật đều ở trạng thái $1$ hoặc $2$, ta chọn ra $3$ bóng đèn bật và thực hiện $2$ thao tác để tắt tất cả chúng:

$$(1\ 1\ 1)\rightarrow (0\ 2\ 1)\rightarrow (0\ 0\ 0)$$

$$(2\ 2\ 2)\rightarrow (0\ 1\ 2)\rightarrow (0\ 0\ 0)$$

Như vậy đáp án sẽ bằng $min(b,c)+\frac{2\times (b+c-2min(b,c))}3$.

**Độ phức tạp:** $O(1)$.

### Subtask 3: $Q\le 5$

Ta cải tiến ý tưởng từ subtask 1. Rõ ràng ta không cần phải quan tâm trạng thái của tất cả bóng đèn mà chỉ cần quan tâm xem có bao nhiêu bóng đèn đang ở trạng thái $0,1,2$. Vì thế nên ta có ý tưởng BFS mới như sau:

Ta sẽ lưu tất cả bộ ba số $(a,b,c)\ (a+b+c=len=R_j-L_j+1)$, mỗi bộ số tương ứng với một state (ta có thể chỉ cần lưu hai trong ba số vì ta dễ dàng xác định được số còn lại).

Coi state $(a_j,b_j,c_j)$ là state xuất phát ($a_j,b_j,c_j$ là số lượng bóng đèn ban đầu ở trạng thái $0,1,2$), ta cần tìm số bước tối thiểu để đưa về state $(len,0,0)$.

Để xác định các state chuyển, ta chỉ cần quan tâm số lượng bóng đèn ở trạng thái $0,1,2$ sẽ thay đổi theo **cách 1, 2**. Trên thực tế, khi đã xác định được số bóng đèn ở trạng thái $0,1$ sẽ thay đổi theo **cách 1, 2** thì số lượng bóng đèn ở trạng thái $2$ cũng sẽ được xác định. Như vậy ta cần $4$ vòng lặp lồng nhau để xét tất cả các state chuyển.

Nhận xét độ phức tạp (tương tự như subtask 1):
- Số state khác nhau (cũng là số đỉnh) tối đa: $n=C^2_{len+2}\le C^2_{N+2}$
- Số state chuyển tối đa với mỗi state: $C^2_{X+2}\times C^2_{Y+2}$
- Số cạnh tối đa của đồ thị: $m\le n\times C^2_{X+2}\times C^2_{Y+2}\le C^2_{N+2}\times C^2_{X+2}\times C^2_{Y+2}$

**Độ phức tạp:** $O\left(Q\times N^2\times P\right)$, với $P$ là số state chuyển tối đa ($P_{max}=60$ trong trường hợp $X=2,Y=3$ hoặc $X=3,Y=2$).

### Subtask 4: Không có ràng buộc gì thêm

Tương tự subtask 1, ta có thể thực hiện BFS ngược thay vì làm như đã nói ở trên. Như vậy ta có thể xử lý mọi yêu cầu khảo sát có $len=R_j-L_j+1$ giống nhau, tương đương với việc ta chỉ cần thực hiện BFS tối đa $N$ lần tương ứng với các giá trị $len$ từ $1$ đến $N$.

**Độ phức tạp:** $O\left(N^3\times P\right)$.

Tuy nhiên, ta vẫn không thể đảm bảo thuật toán này đủ để chúng ta AC. Vì thế nên ta cần có một số cải tiến.

*Lưu ý: Đây là cách làm của mình và có thể còn một số cách làm khác nữa.*

Gọi $f_{b,c}\ (b+c\le len)$ là số thao tác tối thiểu để từ state $(len,0,0)$ đến được state $(len-b-c,b,c)$. Khi tăng $len$ lên $1$ đơn vị, trên thực tế ta không cần phải reset mảng $f$ để thực hiện BFS lại từ đầu mà chỉ cần BFS lại từ một số vị trí.

Tại sao cách này lại hoạt động? Vì cơ bản khi tăng $len$ lên, ta dễ dàng nhận thấy:
- Mỗi đỉnh ta chỉ quan tâm hai giá trị tương ứng là $b,c$ nên số đỉnh của đồ thị sẽ tăng lên.
- Đồng thời, với mỗi đỉnh, số cạnh nối cũng sẽ tăng lên. Một state có thể chuyển sang state khác phụ thuộc vào việc có đủ số bóng đèn với trạng thái tương ứng hay không để thực hiện thao tác, khi tăng $len$ lên, chỉ có $a=len-b-c$ tăng, còn $b$ và $c$ thì không bị ảnh hưởng nên điều này đúng.

Như vậy cấu trúc đồ thị mới khi tăng $len$ sẽ chỉ thêm đỉnh và cạnh, điều này làm giảm độ dài đường đi ngắn nhất giữa các cặp đỉnh với nhau, nên việc BFS lại không làm ảnh hưởng gì hết.

Vậy ta sẽ BFS lại trên các đỉnh nào? Ta chỉ BFS trên các đỉnh có thêm cạnh sau khi tăng $len$ lên. Với các đỉnh không có thêm cạnh nào thì việc BFS lại là vô nghĩa vì nếu có thể BFS sang đỉnh khác thì nó đã được thực hiện ở lượt trước rồi.

Dễ dàng nhận thấy với các đỉnh có $1\le a\le X+Y$ là các đỉnh thỏa mãn vì số bóng đèn tối đa cần đổi trạng thái chỉ là $X+Y$. Như vậy sẽ có xấp xỉ $len\times (X+Y)$ đỉnh cần BFS lại với mỗi lần xét giá trị $len$ mới.

Trên thực tế, tổng số lần thăm BFS tối đa chỉ xấp xỉ $2\times 10^6$ (đã thử trên máy) nên độ phức tạp đã giảm đi đáng kể.

**Độ phức tạp:** $O(S\times P)$, với $S$ là số lần duyệt BFS.

## Bài 2: Quà Noel (GIFT)

### Tóm tắt đề bài

Cho $N$ loại quà, trong đó loại quà thứ $i$ có $S_i$ món với khối lượng mỗi món là $W_i$. Ông già Noel có ý định tạo ra các túi quà để tặng cho các bạn nhỏ, mỗi túi quà phải có đúng $K$ món quà sao cho không có hai món quà nào thuộc cùng một loại.

Bạn đóng vai trợ lý phải trả lời $Q$ câu hỏi của ông già Noel, với mỗi câu hỏi thuộc một trong hai loại như sau:
- **Loại 1** $(1\ M\ K\ T)$: Kiểm tra xem có thể tạo ra $T$ túi quà sao cho tổng khối lượng của tất cả món quà được chọn không vượt quá $M$ hay không.
- **Loại 2** $(2\ M\ K)$: Xác định số lượng túi quà tối đa có thể tạo được sao cho tổng khối lượng của tất cả món quà được chọn không vượt quá $M$.

### Giới hạn và subtask
- $1\le N,Q\le 10^5$
- $1\le W_i\le 10^5$ với mọi $i$ từ $1$ đến $N$
- $1\le S_i\le 10^5$ với mọi $i$ từ $1$ đến $N$
- $1\le M,K,T\le 10^9$ với mọi câu hỏi loại 1
- $1\le M,K\le 10^9$ với mọi câu hỏi loại 2

| Subtask | Điểm | Giới hạn |
|---------|--------|----------|
|1 |$25\%$ |$S_i=1$ với mọi $i$ từ $1$ đến $N$|
|2 |$20\%$ |$N,Q\le 1000$ và chỉ có câu hỏi loại 1|
|3 |$15\%$ |$N,Q\le 1000$|
|4 |$20\%$ |Chỉ có câu hỏi loại 1|
|5 |$20\%$ |Không có ràng buộc gì thêm|

### Subtask 1: $S_i=1$ với mọi $i$ từ $1$ đến $N$

Trong subtask này, mỗi loại quà chỉ có một món quà nên ta không cần phải quan tâm điều kiện thứ hai của việc chọn túi quà (không được có hai món quà nào cùng loại quà).

Xét câu hỏi loại 1, ta áp dụng tham lam bằng cách sắp xếp lại các món quà theo khối lượng tăng dần. Với mỗi túi quà, ta ưu tiên chọn các món quà có khối lượng bé nhất.

Như vậy ta có thể thấy:
- Trong lần chọn đầu tiên, hiển nhiên ta sẽ lấy $K$ món quà bé nhất để bỏ vào túi thứ nhất.
- Trong lần chọn thứ hai, ta lấy các món quà bé thứ $K+1,K+2,\dots,2K$ để bỏ vào túi thứ hai.
- Cứ tiếp tục như vậy, trong lần chọn thứ $T$, ta lấy các món quà có khối lượng bé thứ $(T-1)\times K+1,(T-1)\times K+2,\dots,T\times K$ bỏ vào túi thứ $T$.

Điều này tương đương rằng với câu hỏi loại 1, phương án tối ưu sẽ là chọn ra $K\times T$ món quà có khối lượng bé nhất để lấy tổng và kiểm tra.

**Lưu ý:** Cần phải kiểm tra điều kiện $K\times T\le N$ để đảm bảo việc lấy quà là hợp lệ.

Để giải quyết câu hỏi loại 1 nhanh, ta có thể áp dụng mảng tổng dồn (prefix sum).

Xét câu hỏi loại 2, ta có thể giải quyết bằng chặt nhị phân. Khi xét đến một giá trị $mid$ trong quá trình chặt, điều kiện kiểm tra lại đưa về một câu hỏi loại 1.

**Độ phức tạp:** $O\left((N+Q)\times log(N)\right)$.

### Subtask 2: $N,Q\le 1000$ và chỉ có câu hỏi loại 1

Từ subtask này, mỗi loại quà có thể có nhiều hơn một món quà nên bài toán đã trở nên phức tạp hơn.

Quay trở lại với câu hỏi loại 1, ta vẫn có thể áp dụng tham lam để thực hiện chọn quà nhằm đạt tổng khối lượng tối thiểu:
- Đầu tiên, ta sắp xếp các loại quà theo khối lượng tăng dần.
- Mỗi lần chọn, ta lấy một món quà từ $K$ loại quà có khối lượng bé nhất sao cho mỗi loại đều còn ít nhất một món quà có thể dùng.

Từ cách tham lam trên, ta có thể suy ra công thức lấy tổng khối lượng như sau:
- Vì có $T$ túi kích thước $K$ nên ta cần chọn $K\times T$ hộp quà, gọi $res$ là số lượng hộp còn lại cần lấy.
- Xét từ loại quà có khối lượng bé nhất đến lớn nhất, ta lấy $min(S,T,res)$ hộp quà từ loại quà đang xét và cộng vào tổng khối lượng, sau đó cập nhật $res:=res-min(S,T,res)$.

> **Chứng minh:**
> - Ta có thể thấy với mỗi loại quà, ta chỉ có thể chọn tối đa $T$ hộp quà để bỏ vào tối đa $T$ túi quà khác nhau. Để tối ưu thì rõ ràng với loại quà có khối lượng bé nhất đang xét, ta phải lấy càng nhiều càng tốt.
> - Tại sao cách tham lam trên lại đúng và đảm bảo có cách xếp hộp vào các túi? Nếu xếp các hộp quà theo thứ tự lấy từ công thức trên, thì các hộp quà cùng loại sẽ ở nằm trên một đoạn liên tiếp.
> - Ta có phương án bỏ quà vào túi như sau: bỏ hộp quà đầu tiên vào túi $1$, hộp quà thứ hai vào túi $2$, ..., hộp quà thứ $T$ vào túi $T$, hộp quà thứ $T+1$ vào túi $1$, hộp quà thứ $T+2$ vào túi $2$, ..., hộp quà thứ $x$ vào túi $(x-1)\ mod\ T+1$.
> - Cách này đảm bảo mỗi túi quà chứa các hộp quà thuộc các loại khác nhau vì với mỗi loại quà, các hộp quà cùng loại chỉ nằm liên tiếp trên một đoạn, và vì không có quá $T$ hộp quà cùng một loại nên việc hai hộp quà cùng loại chung một túi sẽ không xảy ra.

Với công thức đã chứng minh, ta có thể giải quyết các câu hỏi loại 1 trong $O(N)$.

**Lưu ý:** Ta cần phải kiểm tra điều kiện $res=0$ sau khi áp dụng công thức để đảm bảo tính hợp lệ của việc lấy quà.

**Độ phức tạp:** $O\left(Q\times N+N\times log(N)\right)$.

### Subtask 3: $N,Q\le 1000$

Như đã nói ở subtask 1, các câu hỏi loại 2 có thể giải quyết bằng chặt nhị phân.

**Độ phức tạp:** $O\left(Q\times N\times log(sum(S))\right)$.

### Subtask 4: Chỉ có câu hỏi loại 1

Vì giới hạn lớn, ta không thể giải quyết các câu hỏi loại 1 bằng cày trâu như subtask 2 được nữa.

Giả sử ta đã sắp xếp các loại quà theo khối lượng tăng dần, gọi hai dãy $F$ và $G$ có công thức như sau:

$$F_i=F_{i-1}+min(S_i,T)$$

$$G_i=G_{i-1}+W_i\times min(S_i,T)$$

Ta có thể chặt nhị phân vị trí $x$ lớn nhất sao cho $F_x\le K\times T$ và tổng sẽ bằng $G_x+W_{x+1}\times (K\times T-F_x)$. Tuy nhiên, ta cần phải phá điều kiện $min(S_i,T)$ để có cách giải quyết tốt hơn do mỗi câu hỏi loại 1 lại có giá trị $T$ khác nhau.

Ta thấy nếu $S_i\le T$ thì $min(S_i,T)=S_i$, ngược lại $min(S_i,T)=T$. Như vậy ta có thể tách phần tính tổng làm hai phần, phần đầu tiên là tổng của $S_i$ với $S_i\le T$, phần thứ hai là số giá trị $S_i>T$ nhân với $T$.

Ta sẽ xử lý các câu hỏi một cách offline để giải quyết subtask này. Với mảng $F$, ta tạo hai segment tree/fenwick tree để quản lý tổng và số lượng đã được mô tả ở trên. Mảng $G$ cũng thực hiện tương tự.

Đầu tiên, ta sắp xếp các câu hỏi theo $T$ tăng dần. Ban đầu, ta coi $T=0$ thì tất cả các giá trị $S_i$ đều lớn hơn $T$. Khi xét đến câu hỏi có $T=T'$, ta cập nhật lại các vị trí mới thỏa mãn $S_i\le T$.

Để có thể làm việc này một cách dễ dàng, ta sắp xếp các chỉ số $i$ theo $S_i$ tăng dần. Khi tăng $T$ lên thì ta chỉ cần cập nhật lại các chỉ số tiếp theo thỏa mãn.

Sau khi cập nhật, ta đã có đủ thông tin để truy vấn các phần tử trên dãy $F$ và $G$. Để tìm nhanh chỉ số $x$ thỏa mãn như đã nói, ta áp dụng walk on segment tree/fenwick tree. Sau đó ta thực hiện truy vấn giá trị của $G_x$ để xác định tổng khối lượng tối ưu cần tìm.

Các thao tác cập nhật, truy vấn, walk đều có thể thực hiện trong $O(log(N))$.

**Độ phức tạp:** $O\left((N+Q)\times log(N)\right)$.

### Subtask 5: Không có ràng buộc gì thêm

Vì tính chất offline của việc giải quyết các câu hỏi loại 1, ta không thể áp dụng chặt nhị phân bình thường được. Thay vào đó, ta sẽ thực hiện chặt nhị phân song song trên tập các câu hỏi loại 2.

**Độ phức tạp:** $O\left((N+Q)\times log(N)\times log(sum(S))\right)$.

## Bài 3: Bài đăng (POST)

### Tóm tắt đề bài

Cho dãy số $A$ gồm $N$ phần tử. Bạn cần phải giải quyết $Q$ truy vấn, với truy vấn thứ $j$:
- Gồm hai số nguyên dương $U_j$ và $V_j$, yêu cầu đếm số cặp số $(L,R)$ sao cho:
- $U_j\le L\le R\le V_j$.
- Không tồn tại hai giá trị $p,q$ sao cho $p\in [L;R],q\notin [L;R], A_p=A_q$.

### Giới hạn và subtask
- $1\le N,Q\le 3\times 10^5$
- $1\le A_i\le 10^9$ với mọi $i$ từ $1$ đến $N$
- $1\le U_j\le V_j\le N$ với mọi $j$ từ $1$ đến $Q$

| Subtask | Điểm | Giới hạn |
|---------|--------|----------|
|1 |$15\%$ |$N,Q\le 50$|
|2 |$15\%$ |$N\le 500$|
|3 |$10\%$ |$N\le 5000$|
|4 |$20\%$ |$Q=1;U_j=1;V_j=N$|
|5 |$20\%$ |$Q\le 30000$|
|6 |$20\%$ |Không có ràng buộc gì thêm|

### Subtask 1: $N,Q\le 50$

Subtask này đơn giản chỉ là làm theo yêu cầu của đề bài.

Mỗi truy vấn ta xét hết các cặp số $(L,R)$ và kiểm tra xem cặp số đang xét có thỏa mãn điều kiện đề bài hay không trong $O(N^2)$.

**Độ phức tạp:** $O(Q\times N^4)$ (lưu ý hằng số rất bé).

### Subtask 2: $N\le 500$

Xét một phần tử $A_x\ (L\le x\le R)$, để thỏa mãn điều kiện đề bài thì các phần tử còn lại có giá trị $A_x$ đều phải nằm trong đoạn $[L;R]$. Nếu gọi $first_v$ và $last_v$ là vị trí của phần tử đầu tiên và cuối cùng có giá trị bằng $v\ (v\in A)$ thì $L\le first_v\le last_v\le R$.

Ta dựng mảng $first$ và $last$ trước. Để kiểm tra đoạn $[L;R]$, ta xét hết các phần tử $A_x\ (L\le x\le R)$ và kiểm tra như trên trong $O(N)$.

Để giải quyết truy vấn nhanh, có 2 cách làm:
- **Cách 1 (prefix sum 2D):** Lưu trước kết quả của đoạn $[L;R]\ (1\le L\le R\le N)$ vào $pref_{L,R}$ ($0/1$ nếu không/có thỏa mãn) và dựng mảng prefix sum 2D. Khi lấy kết quả, ta chỉ cần lấy tổng các phần tử trên vùng hình chữ nhật xuất phát từ hàng $U_j$ đến $V_j$ và từ cột $U_j$ đến $V_j$ trong $O(1)$.
- **Cách 2 (quy hoạch động):** Gọi $dp_{l,r}$ là đáp án bài toán cho trường hợp $U_j=l,V_j=r$; hàm $check(l,r)=0/1$ tương ứng với đoạn $[L;R]$ không/có thỏa mãn. Khi đó ta có công thức:

$$dp_{l,r}=dp_{l+1,r}+dp_{l,r-1}-dp_{l+1,r-1}+check(l,r)$$

**Độ phức tạp:** $O(N^3+Q)$.

### Subtask 3: $N\le 5000$

Ta có thể viết lại điều kiện kiểm tra đoạn $[L;R]$ thành việc kiểm tra hai điều kiện như sau:

$$min(first_{A_L},first_{A_{L+1}},\dots,first_{A_R})\ge L$$

$$max(last_{A_L},last_{A_{L+1}},\dots,last_{A_R})\le R$$

Như vậy, việc kiểm tra có thể thực hiện bằng cách duy trì hai biến $min\_first$ và $max\_last$ và cập nhật chúng khi chuyển từ xét đoạn $[L;R]$ sang đoạn $[L;R+1]$, từ đó việc kiểm tra đoạn độ phức tạp chỉ còn $O(1)$ mỗi đoạn.

**Độ phức tạp:** $O(N^2+Q)$.

### Subtask 4: $Q=1;U_j=1;V_j=N$

Ta coi một đoạn $[x;y]$ tương ứng điểm $(x,y)$ trên mặt phẳng tọa độ. Bây giờ, ta sẽ thực hiện "cấm" một số điểm, tương đương với việc đoạn con đó không thỏa mãn.

Ta sẽ xây dựng các vùng cấm có dạng hình chữ nhật.

Đầu tiên, ta sẽ cấm các điểm có tọa độ $(x,y)$ mà $x > y$ do đây không phải đoạn con. Ta tạo ra $N$ vùng cấm.

Sau đó, ta duyệt qua từng phần tử $A_i$. Lúc này:
- Nếu đoạn $[x;y]$ chứa phần tử $A_i$ thì đoạn cũng phải chứa vị trí $first_{A_i}$ và $last_{A_i}$. Như vậy ta tạo ra hai vùng "cấm":
- Vùng cấm có dạng $x\in[first_{A_i}+1;i],y\in [i,N]$: Cấm các đoạn chứa $i$ nhưng không chứa $first_{A_i}$.
- Vùng cấm có dạng $x\in[1;i],y\in [i,last_{A_i}-1]$: Cấm các đoạn chứa $i$ nhưng không chứa $last_{A_i}$.

Sau khi đã xây được các vùng cấm, ta sẽ cần đếm số điểm trên mặt phẳng mà không bị vùng nào cấm. Ta có thể giải bằng thuật toán Sweep Line, tương tự bài [AREA](https://oj.vnoi.info/problem/area).

**Độ phức tạp:** $O\left(N\times log(N)\right)$.

### Subtask 5+6: Không có ràng buộc gì thêm

#### Cách 1: Xor hash+Mo's algorithm

Ta sẽ thay đổi cách tiếp cận của bài toán: Với mọi giá trị $v$ xuất hiện trong dãy $A$, gọi $p_1,p_2,\dots,p_k$ là các vị trí trong dãy có $A_{p_i}=v$, ta gán cho mỗi vị trí một giá trị **ngẫu nhiên** $value_{p_i}$ sao cho:

$$value_{p_1}\oplus value_{p_2}\oplus \dots\oplus value_{p_k}=0$$

Như vậy ta có thể xác định tính thỏa mãn của đoạn $[L;R]$ bằng điều kiện sau:

$$value_L\oplus value_{L+1}\oplus \dots\oplus value_R=0$$

Áp dụng tính chất của phép toán XOR, nếu gọi $pref_i=pref_{i-1} \oplus value_i$ thì điều kiện có thể viết lại thành $pref_R\oplus pref_{L-1}=0$, hay $pref_R=pref_{L-1}$.

Tới đây thì bài toán lại đưa về dạng đếm số cặp phần tử $(L,R)\ (U-1\le L<R\le V)$ sao cho $pref_L=pref_R$. Đây là một bài toán đếm số cặp phần tử bằng nhau kinh điển có thể giải quyết bằng thuật toán Mo's algorithm.

**Độ phức tạp:** $O\left((N+Q)\times \sqrt N\right)$.

#### Cách 2: Sweep line+Walk on Segment Tree+Mo's algorithm

**Nhận xét:** Nếu đoạn $[a;b]$ và đoạn $[b+1;c]$ đều thỏa mãn thì đoạn $[a;c]$ cũng thỏa mãn.

Ta có ý tưởng giải quyết bài toán như sau:
- Với mọi giá trị $i\ (1\le i\le N)$, ta tìm giá trị $nex_i$ nhỏ nhất sao cho đoạn $[i;nex_i]$ thỏa mãn điều kiện của đề bài.
- Khai thác từ nhận xét ở trên, ta chia các đoạn $[i;nex_i];[nex_i+1;nex_{nex_i+1}];\dots$ làm một nhóm. Khi đó nếu truy vấn $(U,V)$ có $k$ đoạn trong nhóm này hoàn toàn trong đoạn $[U;V]$ thì đáp án sẽ tăng lên $\frac{k\times (k+1)}2$.

Ta áp dụng Sweep Line như đã mô tả ở subtask 4 và sử dụng Walk on Segment Tree để tìm ra các giá trị $nex_i$. Khi đã tìm được các giá trị trên, ta cũng có thể áp dụng Mo's algorithm để giải quyết phần còn lại của bài toán.

**Độ phức tạp:** $O\left((N+Q)\times \sqrt N+N\times log(N)\right)$.

#### Cách 3: Sweep line+Lazy Segment Tree

Nhắc lại các vùng cấm ở subtask 4:

**1. Vùng cấm có dạng $x\in[1;i],y\in [i,last_{A_i}-1]$:**

Giữ $y$ cố định, tất cả các vùng cấm dạng này sẽ cấm một đoạn **prefix theo trục $x$**, vì luôn bắt đầu từ $x=1$.

Ta gọi $C_y = max(i)$ mà $i\le y<last_{A_i}$. Lúc này, đoạn $[x; y]$ muốn thỏa mãn phải có $x > C_y$.

**2. Vùng cấm có dạng $x\in[first_{A_i}+1;i],y\in [i,N]$:**

Tương tự, đặt $R_x = min (i)$ mà $first_{A_i} < x \le i$, nếu không có thì $R_x = n + 1$.

Như vậy, đoạn $[x; y]$ muốn thỏa mãn phải có $y<R_x$.

Ta đã chuyển được về hai điều kiện 1D khá đơn giản. Để đoạn $[x; y]$ thỏa mãn thì $x \le y, x > C_y, y < R_x$.

Ta có thể dựng mảng $C$ và mảng $R$ bằng cách sweepline kết hợp với `std::priority_queue` khá đơn giản.

Khi này, ta cần trả lời câu hỏi: cho $u,v$, đếm số cặp $(x, y)$ thỏa mãn $1 \le x \le u$, $x \le y \le v$, và $(x, y)$ thỏa mãn điều kiện trên. Ta sẽ trả lời các câu hỏi này offline.

> Nếu gọi $f(u,v)$ là đáp án bài toán trên với $u,v$ tương ứng thì đáp án cho truy vấn $[U_j;V_j]$ sẽ bằng $f(V_j,V_j)-f(U_j-1,V_j)$.

----------------------

Nhắc lại điều kiện:
- $y < R_x \rightarrow$ với mỗi $x$, chỉ xét $y \in [x; R_x-1]$.
- $x > C_y \rightarrow$ với mỗi $y$, nó chỉ “được phép” từ thời điểm $x = C_y + 1$ trở đi.

Ta thấy:

- Mỗi $y$ có “thời điểm kích hoạt”:
$$
act_y = C_y + 1
$$
- Khi sweep tới $x$, ta **activate** tất cả $y$ có $act_y = x$.
- Sau đó ta muốn “thêm 1 điểm” $(x,y)$ cho mọi $y$ đã active trong đoạn:
$$
y \in [x;R_x-1]
$$
- Đồng thời ta cần truy vấn nhanh:
$$
f(x,b) = \sum_{y=1}^{b} cnt_y
$$
trong đó $cnt_y$ là số $x' \le x$ sao cho $(x',y)$ hợp lệ

Như vậy, ta có thể dùng segment tree lưu:

- $cntActive$ trong node (bao nhiêu $y$ đã active)
- $sum$ = tổng $cnt_y$ của các $y$ active trong node
- range add $+1$ chỉ cộng lên các $y$ active $\rightarrow$ $sum:= sum + 1 \times cntActive$. Ta cần lưu thêm một biến $cntAdd$ lưu số lần range add chưa đẩy xuống các con, khi đẩy xuống thì ta tăng $sum$ của các con lên $cntActive_{child}\times cntAdd$.

Lưu ý thứ tự sweepline, ta có thể làm như sau:

1. Activate tất cả $y$ trong bucket $act[x]$.
2. $U = R_x-1$. Nếu $U \ge x$: $rangeAdd([x; U], +1)$.
3. Trả lời các event tại thời điểm $x$: $querySum([1; b])$.

**Độ phức tạp:** $O\left((N+Q)\times log(N)\right)$.

## Bài 4: Tất niên (TET)

### Tóm tắt đề bài

Với một dãy số $B$ gồm $M$ phần tử, độ đa dạng của dãy bằng số lượng dãy khác nhau có thể tạo được bằng cách thực hiện không quá một phép đảo ngược bất kỳ đoạn con nào trên dãy.

Cho một dãy số $A$ gồm $N$ phần tử, bạn cần phải giải quyết $Q$ truy vấn. Với truy vấn thứ $j$:
- Thực hiện xóa bỏ phần tử thứ $p_j$ trong dãy $A$. Các phần tử còn lại giữ nguyên vị trí ban đầu và tạo thành các đoạn con bị ngăn cách bởi các phần tử bị xóa.
- Xác định độ đa dạng của đoạn con có độ đa dạng lớn nhất trong tất cả đoạn con của dãy $A$.

### Giới hạn và subtask
- $1\le Q<N\le 2\times 10^5$
- $1\le A_i\le 10^9$ với mọi $i$ từ $1$ đến $N$
- $1\le p_j\le N$ với mọi $j$ từ $1$ đến $Q$
- Các phần tử trong dãy $p$ đôi một phân biệt

| Subtask | Điểm | Giới hạn |
|---------|--------|----------|
|1 |$30\%$ |$Q=1;N\le 200$|
|2 |$30\%$ |$Q=1;N\le 2000$|
|3 |$20\%$ |$Q=1$|
|4 |$20\%$ |Không có ràng buộc gì thêm|

### Subtask 1: $Q=1;N\le 200$

Với một dãy số $B$ độ dài $M$, có $\frac{M\times (M+1)}2+1$ cách thực hiện thao tác khác nhau để tạo ra các dãy ($1$ cách không đảo ngược đoạn con và $\frac{M\times (M+1)}2$ cách đảo ngược một đoạn con).

Xét bài toán xác định độ đa dạng của đoạn con/dãy. Cách làm đơn giản nhất là tạo ra tất cả dãy và đếm số dãy khác nhau bằng cày trâu. Tuy nhiên, độ phức tạp cho cách làm này là quá lớn kể cả với subtask 1.

Thay vào đó, ta sẽ sử dụng hash để nén các dãy số thành các số nguyên không âm, cách nén y hệt so với cách nén xâu:

$$hash=\left(\sum_{i=1}^M B_i\times base^{M-i}\right)\ mod\ MOD$$

Bằng cách này, bài toán giờ chỉ là đếm số lượng phần tử khác nhau của một dãy số nguyên không âm và có thể giải trong $O\left(M\times S+S\times log(S)\right)$ với $S$ là số lượng dãy khác nhau có thể tạo.

Trong ba subtask đầu, vì $Q=1$ nên ta chỉ cần tính độ đa dạng của tối đa hai đoạn con trong dãy và xác định giá trị lớn hơn.

**Lưu ý:** Để chắc chắn, các bạn có thể cải đặt từ $2$ giá trị $MOD$ khác nhau trở lên.

**Độ phức tạp:** $O(N^3+N^2\times log(N))$.

### Subtask 2: $Q=1;N\le 2000$

Ta có thể cải tiến cách tính giá trị $hash$. Ta tạo hai mảng lưu trữ các giá trị $hash$ tiền tố của mảng $B$ và mảng $B$ theo thứ tự ngược lại.

Ta tính trước giá trị $hash$ của toàn bộ dãy. Khi đảo ngược đoạn $[L;R]$, ta dùng hai mảng vừa tạo để trừ $hash$ của đoạn và cộng lại $hash$ của đoạn sau khi đã đảo ngược. Vì thế nên độ phức tạp cho việc tính giá trị $hash$ trong các trường hợp đảo ngược đoạn chỉ còn $O(1)$, độ phức tạp cho việc tính độ đa dạng của mảng đã cải tiến xuống $O\left(S\times log(S)\right)$.

**Độ phức tạp:** $O(N^2\times log(N))$.

### Subtask 3: $Q=1$

Ta không thể thực hiện cày trâu như hai subtask trên nữa. Liệu có cách nào để xác định độ đa dạng của dãy một cách nhanh chóng hay không?

**Nhận xét:** Độ đa dạng của dãy số $B$ độ dài $M$ bằng số cặp số $(x,y)$ $(1\le x<y\le M)$ sao cho $B_x\ne B_y$ cộng $1$.

> **Chứng minh:**
> - Dãy gốc được tính là một dãy do ta có thể không thực hiện đảo ngược hoặc đảo ngược đoạn chỉ gồm $1$ phần tử.
> - Xét mọi cặp số $(x,y)$ có $B_x\ne B_y$, khi đảo ngược đoạn $[x;y]$ sẽ luôn tạo ra một dãy mới.
> - Tại sao? Giả sử ta chỉ quan tâm vị trí phần tử đầu tiên và phần tử cuối cùng bị thay đổi, nếu cặp vị trí mà khác nhau thì hai dãy tạo được cũng sẽ khác nhau. Rõ ràng khi đảo đoạn $[x;y]$ thì hai vị trí đầu và cuối bị thay đổi sẽ là $x$ và $y$. Từ đó có thể suy ra điều vừa nói ở trên.
> - Xét mọi cặp số $(x,y)$ có $B_x=B_y$, dễ dàng nhận thấy khi đảo ngược đoạn $[x;y]$ hay đoạn $[x+1;y-1]$ thì đều như nhau. Như vậy việc đảo ngược đoạn $[x;y]$ với mọi cặp số trong trường hợp này đều không tạo ra dãy mới.
>
> Từ những điều trên ta suy ra điều cần chứng minh. Như vậy bài toán đã đơn giản hơn rất nhiều.

Ta có thể thay đổi cách tính bằng công thức $\frac{M\times (M-1)}2-S+1$ với $S$ là số cặp số $(x,y)\ (1\le x<y\le M)$ sao cho $B_x=B_y$. Bài toán giờ trở về bài toán đếm số cặp phần tử bằng nhau cơ bản.

**Độ phức tạp:** $O\left(N\times log(N)\right)$.

### Subtask 4: Không có ràng buộc gì thêm

Có $2$ cách làm cho subtask này.

#### Cách 1: DSU+Small to large

Ta có thể đảo ngược cách thực hiện truy vấn. Giả sử ta có dãy sau khi thực hiện các truy vấn, mỗi bước ta thêm lại một phần tử vô dãy. Khi đó, một số đoạn con sẽ gộp lại trở thành đoạn con lớn hơn. Tới đây ta thấy bài toán có thể giải quyết bằng thuật toán DSU.

Mỗi đoạn con ta duy trì một CTDL lưu trữ số lần xuất hiện của các phần tử và số cặp phần tử bằng nhau trong đoạn con đó.

Khi gộp hai đoạn con, số cặp phần tử bằng nhau mới tạo được sẽ bằng $\sum_{x\in S}cnta_x\times cntb_x$ ($S$ là tập các phần tử phân biệt trong đoạn con thứ nhất, $cnta_x$ và $cntb_x$ là số lần xuất hiện của $x$ trong đoạn con thứ nhất và hai).

Để cải tiến, ta áp dụng kỹ thuật small to large: Thực hiện cập nhật từ tập hợp bé sang tập hợp lớn.

Cuối cùng, ta dùng một `std::multiset` để duy trì độ đa dạng của các đoạn con và lấy giá trị của số lớn nhất trong tập.

**Độ phức tạp:** $O\left(N\times log^2(N)+Q\times log(N)\right)$.

#### Cách 2: Mo's algorithm

Khi ta xóa một phần tử, một đoạn con của dãy sẽ bị chia làm tối đa hai đoạn con khác nhau. Điều này tương đương với việc sau mỗi truy vấn, sẽ có thêm tối đa hai đoạn con khác nhau cần phải xác định độ đa dạng. Có tối đa $2Q+1$ đoạn con cần xét.

Tới đây thì bài toán lại đưa về dạng như sau:

> Cho dãy số $A$ gồm $N$ phần tử và $Q$ truy vấn, mỗi truy vấn gồm hai số nguyên dương $L,R$. Với mỗi truy vấn, hãy đếm số cặp số $(x,y)\ (L\le x<y\le R)$ sao cho $A_x=A_y$.

Đây là một bài toán sử dụng Mo's algorithm điển hình. Phần còn lại của bài toán chỉ là dùng một `std::multiset` để duy trì độ đa dạng của các đoạn con và lấy giá trị của số lớn nhất trong tập.

**Độ phức tạp:** $O\left((N+Q)\times \sqrt N+Q\times log(N)\right)$.

## Bài 5: Cây thông (PINE)

### Tóm tắt đề bài

Cho một cây gồm $N$ đỉnh, đỉnh thứ $i$ có trọng số là $A_i$. Bạn cần phải giải quyết $Q$ truy vấn, với truy vấn thứ $j$:
- Gồm ba số nguyên dương $x_j,y_j,w_j$. Xét mọi đỉnh $v$ trên đường đi ngắn nhất từ $x_j$ tới $y_j$, cập nhật $A_v:=A_v\ mod\ w_j$.
- Yêu cầu xác định giá trị của $\sum_{i=1}^N A_i\ mod\ j$.

### Giới hạn và subtask
- $1\le N,Q\le 2\times 10^5$
- $0\le A_i\le 2\times 10^5$ với mọi $i$ từ $1$ đến $N$
- Các cạnh $(u,v)\ (1\le u,v\le N,u\ne v)$ trong $N-1$ cạnh thỏa mãn tạo thành cây
- $1\le x_j,y_j\le N$ với mọi $j$ từ $1$ đến $Q$
- $1\le w_j\le N$ với mọi $j$ từ $1$ đến $Q$

| Subtask | Điểm | Giới hạn |
|---------|--------|----------|
|1 |$20\%$ |$N,Q\le 5000$|
|2 |$20\%$ |$A_i\le 2$ với mọi $i$ từ $1$ đến $N$; $(\dagger)$|
|3 |$20\%$ |$x_j=y_j$ với mọi $j$ từ $1$ đến $Q$; $(\dagger)$|
|4 |$20\%$ |$(\dagger)$|
|5 |$20\%$ |Không có ràng buộc gì thêm|

$\dagger$: Tồn tại cạnh nối giữa hai đỉnh $i$ và $i+1$ với mọi $i$ từ $1$ đến $N-1$.

### Subtask 1: $N,Q\le 5000$

Subtask này đơn giản chỉ là làm theo yêu cầu đề bài.

Với mỗi truy vấn, ta duyệt qua tất cả đỉnh trên đường đi ngắn nhất từ $x_j$ đến $y_j$ và thực hiện cập nhật, sau đó for trâu để lấy đáp án.

Việc duyệt đỉnh có thể thực hiện bằng DFS hoặc BFS (cần cái đặt khéo léo một xí do hằng số cao).

**Độ phức tạp:** $O(Q\times N)$.

### Subtask 2: $A_i\le 2$ với mọi $i$ từ $1$ đến $N$; $(\dagger)$

Với điều kiện $(\dagger)$, bài toán trên cây giờ chỉ còn là bài toán trên dãy số, và mỗi truy vấn là một truy vấn đoạn. **Tuy nhiên vì đề không nói gì về thông tin $x_j\le y_j$ nên khi thực hiện truy vấn phải đổi giá trị của chúng trong trường hợp cần thiết để thuận tiện xử lý.**

**Nhận xét 1:** Nếu $a\ge b$ thì $a\ mod\ b<a$, ngược lại $a\ mod\ b=a$.

Ta có thể thấy khi thực hiện phép modulo, giá trị của $A_i$ luôn giảm dần. Nếu trong mỗi truy vấn, ta chỉ quan tâm những đỉnh mà **chắc chắn** sẽ bị thay đổi thì số thao tác cập nhật lại tối đa sẽ là $2N$ (do giới hạn đặc biệt của subtask là $A_i\le 2$).

Do $A_i\le 2$, ta có thể tạo hai CTDL lưu trữ vị trí của các số $1,2$ trên dãy $A$ (ta không cần xét các số $0$ vì giá trị của các phần tử đó không bao giờ thay đổi nữa). Khi xét truy vấn $(x_j,y_j,w_j)\ (u_j\le v_j)$, ta tìm vị trí của các phần tử lớn hơn hoặc bằng $w_j$ trong đoạn $[x_j;y_j]$ và cập nhật lại dựa trên các CTDL đã tạo.

Để trả lời truy vấn, ta áp dụng đếm phân phối để duy trì số lượng số $0,1,2$ trong dãy và lấy kết quả trong $O(1)$.

**Độ phức tạp:** $O\left((N+Q)\times log(N)\right)$ (có thể khác tùy vào CTDL sử dụng).

### Subtask 3: $x_j=y_j$ với mọi $j$ từ $1$ đến $Q$; $(\dagger)$

Định nghĩa giá trị $M=2\times 10^5$.

Do mỗi truy vấn, ta chỉ cập nhật lại một đỉnh nên ta không cần phải để ý vấn đề cập nhật nhanh. Tuy nhiên, ta cần phải quan tâm tới vấn đề thứ hai của bài toán: Tính kết quả nhanh.

Ta xét bài toán con đơn giản hơn: Giả sử dãy $A$ luôn không đổi sau các truy vấn, và ta cần xác định các giá trị $\sum_{i=1}^n A_i\ mod\ j$ với mọi $j$ từ $1$ đến $Q$.

Ta có một nhận xét như sau:

**Nhận xét 2:** $a\ mod\ b=a-\lfloor\frac{a}b \rfloor\times b$.

Từ nhận xét trên, ta có thể đưa bài toán về việc tính $\sum_{i=1}^n A_i-\left(\sum_{i=1}^n \lfloor\frac{A_i}j\rfloor \right)\times j$.

Xét phép toán $\sum_{i=1}^n \lfloor\frac{A_i}j\rfloor$, ta có thể xét mọi khoảng $[j\times t,j\times (t+1))$ $(j\times t\le M)$ và đếm số lượng phần tử có giá trị trong khoảng đó rồi nhân với $t$ để cộng vào tổng. Việc này có thể giải quyết bằng prefix sum.

Với mỗi số $j$, ta cần khoảng $\frac{M}j$ lần lấy tổng như trên. Vì thế nên số lần lấy tổng với mọi $j$ từ $1$ đến $M$ sẽ bằng $\sum_{i=1}^{M} \frac{M}i\approx M\times log(M)$ (đây là harmonic sum, các bạn có thể tìm hiểu trên mạng để hiểu rõ hơn).

Quay trở lại bài toán, thay vì dùng prefix sum, ta tạo một fenwick tree để quản lý số lần xuất hiện của các phần tử trong dãy. Khi xét truy vấn thứ $j$, ta cập nhật lại mảng tần số trong $O(log(M))$ và lấy tổng $\frac{M}j$ lần.

**Độ phức tạp:** $O\left(M\times log^2(M)\right)$.

### Subtask 4: $(\dagger)$

Ta có thêm một nhận xét về phép $mod$ như sau:

**Nhận xét 3:** Với mỗi phần tử $A_i$, số lần thay đổi tối đa sẽ xấp xỉ $log(A_i)$.

> **Chứng minh:** Xét phép $A_i\ mod\ w\ (A_i\ge w)$. Có $2$ trường hợp như sau:
> - Nếu $\lfloor \frac{A_i}2\rfloor<w\le A_i\rightarrow A_i\ mod\ w=A_i-w\le \lfloor \frac{A_i}2\rfloor$.
> - Nếu $1\le w\le \lfloor \frac{A_i}2\rfloor\rightarrow A_i\ mod\ w<w\le \lfloor \frac{A_i}2\rfloor$.
>
> Như vậy sau mỗi lần cập nhật $A_i:=A_i\ mod\ w$, giá trị này sẽ luôn nhỏ hơn hoặc bằng một nửa. Suy ra điều cần chứng minh.

Từ nhận xét trên, ta có thể thấy số lần thay đổi tối đa của các phần tử trong dãy $A$ chỉ xấp xỉ $N\times log(M)$.

Để cập nhật nhanh, ta dùng một segment tree để quản lý giá trị và vị trí của phần tử lớn nhất trong đoạn. Khi xét truy vấn $(x_j,y_j,w_j)\ (x_j\le y_j)$:
- Chọn phần tử lớn nhất trong đoạn $[x_j;y_j]$. Nếu phần tử đó lớn hơn hoặc bằng $w_j$, thực hiện cập nhật lại phần tử đó. Nếu không thì ta biết đoạn $[x_j;y_j]$ đã hết phần tử cần phải cập nhật.
- Mỗi khi cập nhật một phần tử, ta cũng cập nhật lại mảng tần số trên fenwick tree.
- Thực hiện thao tác trên đến khi không còn phần tử nào lớn hơn hoặc bằng $w_j$ trong đoạn nữa.

Tất cả thao tác trên segment tree/fenwick tree đã nói ở trên đều có độ phức tạp là $O(log(N))$.

**Độ phức tạp:** $O\left(N\times log(N)\times log(M)+M\times log^2(M)\right)$.

### Subtask 5: Không có ràng buộc gì thêm

Để có thể giải được subtask cuối, ta vẫn sử dụng ý tưởng của subtask 4, đồng thời áp dụng thuật toán Heavy-Light Decomposition để có thể giải được trên cây.

**Độ phức tạp:** $O\left(N\times log(N)\times log(M)+M\times log^2(M)\right)$.