LQDOJ CUP 2022 - Round 3

Trong tiết khoa học máy tính hôm nay, Tí đã học về cây tìm kiếm nhị phân. Cây tìm kiếm nhị phân là một cấu trúc dữ liệu rất thuận lợi cho bài toán tìm kiếm. Một cây tìm kiếm nhị phân gồm các giá trị \(w_{u}\) phân biệt có tính chất sau:

• Mỗi đỉnh có tối đa hai đỉnh con (trái và phải).
• Với mỗi đỉnh \(u\), các đỉnh \(v\) ở cây con bên trái đều có giá trị nhỏ hơn \(u\) (\(w_{u} > w_{v}\)).
• Với mỗi đỉnh \(u\), các đỉnh \(v\) ở cây con bên phải đều có giá trị lớn hơn \(u\) (\(w_{u} < w_{v}\)).

Nhận thấy đây là một cấu trúc dữ liệu thú vị và mới mẻ, Tí đã nghĩ ra một bài toán sau: Xét một cây nhị phân tìm kiếm gồm \(n\) đỉnh được đánh số từ \(1\) đến \(n\), đỉnh \(u\) có trọng số \(c_u\) và giá trị \(w_{u}\). Tại mỗi đỉnh \(u\), với đỉnh \(v\) (khác \(u\)) là đỉnh thuộc cây con gốc \(u\), đặt \(s_{u} = c_{u} + \sum w_{v}\). Hãy tìm cây nhị phân tìm kiếm có \(\max(s_{1}, s_{2}, \ldots, s_{n})\) nhỏ nhất. Nếu có nhiều cây thỏa mãn, hãy tìm cây có thứ tự từ điển lớn nhất.

Cây \(A\) có thứ tự từ điển lớn hơn cây \(B\) nếu dãy tiền thứ tự của cây \(A\) có thứ tự từ điển lớn hơn cây \(B\).

Dãy tiền thứ tự của một cây có thể thu được bằng cách duyệt các đỉnh theo thứ tự như sau: duyệt đỉnh gốc đầu tiên, sau đó duyệt cây con bên trái và cuối cùng là cây con bên phải.

Dãy \(a\) có thứ tự từ điển lớn hơn dãy \(b\) nếu tồn tại vị trí \(i\) sao cho \(a_{j} = b_{j}\) với mọi \(1 \leq j < i\) và \(a_{i} > b_{i}\).

Input

• Dòng đầu tiên chứa số nguyên \(n\) (\(1 \leq n \leq 10^{5}\)) là số lượng đỉnh của cây tìm kiếm nhị phân.
• Dòng tiếp theo chứa \(n\) số nguyên \(c_{1}, c_{2}, \ldots, c_{n}\) (\(1 \leq c_{i} \leq 10^{9}\)).
• Dòng tiếp theo chứa \(n\) số nguyên \(w_{1}, w_{2}, \ldots, w_{n}\) (\(1 \leq w_{1} < w_{2} < \ldots < w_{n} \leq 10^{9}\)).

Output

• Dòng đầu tiên chứa một số nguyên là \(\max(s_{1}, s_{2}, \ldots, s_{n})\) trong cây tìm kiếm nhị phân tìm được.
• Dòng tiếp theo chứa \(n\) số nguyên là dãy tiền thứ tự của cây.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 4 \times 10^{2}\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \leq 3 \times 10^{3}\).
• Subtask \(4\) (\(40\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
4 3 2 1
1 2 3 4

7
4 3 2 1

6
27 10 44 32 15 41
2 3 4 5 6 7

44
5 4 2 1 3 6

Bảo và Lâm là đôi bạn thân. Cả hai bạn rất đam mê đồ công nghệ nên cả hai muốn đến khu mua sắm công nghệ Shiro. Ở con đường Shiro, có \(n\) cửa hàng xếp thành hàng ngang được đánh số từ \(1\) đến \(n\).

Thời nay, việc tìm hiểu một cửa hàng mà không cần vào trực tiếp ở quầy là một điều dễ dàng. Chỉ cần tìm ra page, web của những cửa hàng đó, bạn có thể tìm trước các sản phẩm mà mình muốn mua thay vì đến tận nơi để xem. Do đó, trước khi đến trung tâm công nghệ Shiro đông đúc, Bảo và Lâm sẽ ở nhà tìm hiểu hết \(n\) cửa hàng và sau đó mới đến tại cửa hàng để mang về. Sau khi đã tính toán xong, cả hai bạn đã thống kê lại lượng tiền cần chi ra đối với cửa hàng thứ \(i\) là \(a_i\) đồng. Và với mọi cửa hàng \(i\), Bảo và Lâm cũng thống nhất rằng nếu đã mua thì phải mua đúng \(a_i\) đồng như đã tính toán ở nhà hoặc là không mua gì cả.

Sau khi đã có bản thống kê chi tiêu, cả hai bạn bắt đầu di chuyển đến khu Shiro để mua sắm. Bảo sẽ chọn cửa hàng bắt đầu di chuyển đó là cửa hàng \(l\), nghĩa là sau đó, cả hai bạn trẻ sẽ đến các cửa hàng \(l+1,l+2,\ldots\) tức là cả hai sẽ tới cửa hàng \(i\) rồi mới sang cửa hàng \(i+1\) và bắt đầu từ vị trí \(l\). Tuy nhiên, lâm nhận thấy rằng lúc này cả hai chỉ có trong tay số tiền là \(k\) đồng nên có thể sẽ không chi tiêu được theo dự định tại tất cả các cửa hàng từ vị trí \(l\) đến vị trí \(n\). vì vậy, Lâm quyết định đưa ra hai giá trị \(u,v\) \((u \le v)\) làm tiêu chí mua sắm. Tại cửa hàng \(i\), nếu giá trị \(a_i\) không nằm trong đoạn \([u,v]\) thì Bảo và Lâm sẽ bỏ qua và tiếp tục di chuyển đến cửa hàng thứ \(i+1\) (nếu \(i<n\)). Ngược lại, với \(u \le a_i \le v\), cả hai bạn sẽ bỏ ra \(a_i\) đồng như dự tính nếu như số tiền còn lại vẫn \((a_i \le k)\). Tuy nhiên, nếu số tiền còn lại không đủ để mua như dự định \((a_i > k)\) thì cả hai sẽ rất buồn chán và đi về luôn mà không quan tâm các cửa hàng sau đó nữa. Đương nhiên nếu mua được theo dự tính thì số tiền mà hai bạn còn lại cho chuyến mua sắm lần này sẽ giảm đi \(a_i\) đồng.

Như vậy, số lượng cửa hàng có thể mua sắm được trong chuyến đi lần này phụ thuộc vào việc cả hai bạn chọn \(l,u,v\) và số tiền mà cả hai mang theo \(k\). Bạn hãy giúp hai bạn trẻ tính xem số cửa hàng mà các bạn đi qua là bao nhiêu? Lưu ý rằng, những cửa hàng có giá trị \(a_i\) không nằm trong đoạn \([u,v]\) vẫn xem là đi qua vì sau đó cả hai có thể di chuyển tiếp, còn cửa hàng có giá trị \(a_i\) thuộc đoạn \([u,v]\) nhưng lại có \(a_i > k\) thì xem như không đi qua vì đây là cửa hàng làm cho cả hai bạn thất vọng.

Có \(q\) giả thuyết cho các giá trị \(l,u,v,k\) và vẫn dựa trên \(n\) giá trị \(a_1, a_2, \ldots, a_n\) dự định ban đầu của cả hai bạn. Với mỗi giả thuyết, bạn hãy tính xem cả hai bạn Bảo và Lâm sẽ đi qua được bao nhiêu cửa hàng, bạn cần in ra số lượng đó.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) (\(1 \le n, q \le 10^5\)) là số lượng cửa hàng.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)) là \(n\) dự định tương ứng với \(n\) cửa hàng của hai bạn.
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa bốn số nguyên \(l\), \(u\), \(v\), và \(k\) (\(1 \leq l \le n\), \(1 \leq u \le v \le 10^9\), \(1 \leq k \le 10^9\)) mô tả một giả thiết.

Output

• Với mỗi giả thuyết, hãy đưa ra số lượng cửa hàng mà cả hai bạn đi qua.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): Các giả thuyết có \(k\) bằng nhau và \(u=1\), \(v=10^9\).
• Subtask \(2\) (\(20\%\) số điểm): \(a_i \leq 500\) với mọi \(1 \leq i \leq n\).
• Subtask \(3\) (\(20\%\) số điểm): Các giả thiết có \(v - u \le 5\).
• Subtask \(4\) (\(20\%\) số điểm): Các giả thiết có \(u = 1\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

7 3
4 6 8 2 10 5 1
4 1 5 7
1 2 3 5
1 1 10 15

3
7
2

Sau bao năm vất vả học tập và giải những bài toán khó của Alice, Bob bây giờ đã là một quản lý của một công ty lớn. Một ngày đẹp trời nọ, Alice quyết định thăm Bob và cho Bob một bài toán khác để thử thách cậu.

Giả sử công ty của Bob gồm \(n\) nhân viên được đánh chỉ số từ \(1\) đến \(n\) và người thứ \(i\) có năng lực là \(a_i\). Một đội là một nhóm các nhân viên và năng lực của đội đó là tổng XOR (exclusive or) của năng lực của mọi người trong đội. Alice sẽ đưa ra tổng cộng \(q\) yêu cầu, mỗi yêu cầu thuộc một trong hai loại sau:

1. Thay đổi năng lực của nhân viên thứ \(i\) thành \(x\).
2. Đếm số cách chọn một đội mà mỗi nhân viên có chỉ số nằm trong đoạn \([l, r]\) và năng lực của đội đúng bằng \(s\).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 5 \times 10^{4})\) là số lượng nhân viên trong công ty của Bob và số lượng yêu cầu của Alice.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_n\) \((1 \leq a_{i} \leq 10^{6})\) là năng lực của các nhân viên.
• Trong \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên \(i\) và \(x\) \((1 \leq i \leq n, 1 \leq x \leq 10^{6})\) mô tả yêu cầu loại \(1\). Số \(2\) theo sau bởi ba số nguyên \(l\), \(r\) và \(s\) \((1 \leq l \leq r \leq n\), \(1 \leq s \leq 10^{6})\) mô tả yêu cầu loại \(2\).

Output

• Đối với mỗi yêu cầu loại \(2\), in ra một số nguyên trên một dòng là phần dư của số cách chọn thỏa mãn khi chia cho \(10^{9} + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 20\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \leq 10^{3}\), \(a_i \leq 10^{3}\), không có yêu cầu loại \(1\) và mọi yêu cầu loại \(2\) đều có \(l = 1\).
• Subtask \(3\) (\(30\%\) số điểm): \(n, q \leq 10^{3}\).
• Subtask \(4\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

3 3
1 2 3
2 1 3 3
2 1 2 3
2 1 3 1

2
1
2