LQDOJ CUP 2023 - Round 4

Alice và Bob là đôi bạn thân đã lâu. Vào một ngày nọ, vì cảm thấy chán nên Alice quyết định đố Bob một bài toán:

Cho \(n\) cây que, cây que thứ \(i\) \((1 \leq i \leq n)\) có độ dài \(a_{i}\). Hãy đếm số bộ ba cây que sao cho chúng có thể tạo thành ba cạnh một tam giác cân. Biết rằng, hai bộ ba được gọi là khác nhau nếu như tồn tại một cây que thứ \(i\) sao cho cây que thuộc một bộ ba và không thuộc một bộ ba còn lại (\(\{a_{1}, a_{2}, a_{3}\}\) và \(\{a_{3}, a_{2}, a_{1}\}\) là hai bộ ba giống nhau).

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 10^{6})\) là số lượng cây que.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 10^{9})\) là độ dài của các cây que.

Output

• In ra một số nguyên duy nhất là đáp án của bài toán.

Scoring

• Subtask \(1\) (\(42\%\) số điểm): \(n \leq 500\).
• Subtask \(2\) (\(28\%\) số điểm): \(n \leq 5000\) và \(a_{i} \leq 10^{6}\).
• Subtask \(3\) (\(16\%\) số điểm): \(a_{i} \leq 10^{6}\).
• Subtask \(4\) (\(14\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
2 2 3 3 

4

Vào năm 2112, tất cả công việc được chuyên môn hóa, năng suất lao động tăng cực kỳ cao, dẫn tới dư thừa của cải đủ cho gấp đôi dân số vào lúc đó. Vì thế mọi người làm theo năng lực, và hưởng theo nhu cầu.

Vì công việc chuyên môn hóa tới mức độ cao nhất, nên trong việc kinh doanh buôn bán cũng vậy. Ở một khu phố nọ, có \(n\) cửa hàng xếp kề nhau, đánh số từ \(1\) tới \(n\) theo chiều từ đầu tới cuối phố. Mỗi cửa hàng chỉ bán một mặt hàng mang bản sắc riêng của mình, có giá là \(a_{i}\). Để chống cạnh tranh, các mặt hàng phục vụ các nhu cầu khác nhau, và giá cả cũng khác nhau. Để thuận tiện cho người mua hàng dễ tìm kiếm, các chủ tịệm đã cùng nhau thỏa thuận lại vị trí bán hàng, để giá của các mặt hàng giảm dần (nói chính xác thuật ngữ là không tăng) khi đi từ đầu tới cuối phố, hay nói cách khác là \(a_{i} \geq a_{i + 1}\) với mọi \(i\) thỏa mãn \(1 \leq i < n\).

Tuy nhiên, thị trường thế giới đang trong giai đoạn khó khăn, nên dù Sở Giao dịch Hàng hóa Việt Nam (Mercantile Exchange of Vietnam - MXV) rất cố gắng để bình ổn giá, thì nó vẫn lên xuống liên tục như là chơi chứng khoán ở hiện tại. Cứ mỗi lần vật giá tăng, thông tin sẽ được truyền từ MXV tới phố theo hướng từ đầu đường tới cuối đường. Tuy nhiên, người ta có thành ngữ "tam sao thất bản", nên thông tin thường chỉ được truyền tới giữa phố là dừng. Giả sử giá cả tăng lên ít nhất bằng \(y\), và tin truyền tới cửa hàng \(x\), thì với mỗi cửa hàng \(i\) sao cho \(1 \leq i \leq x\), giá sẽ được đổi lại thành \(a_{i} \leftarrow \max(a_{i}, y)\)

Người tiêu dùng tại khu phố này thì đi chợ rất theo nguyên tắc. Họ mang theo \(c\) đồng trong người, và sẽ bắt đầu từ một cửa hàng \(u\) bất kỳ để đi tới cuối phố. Với mỗi cửa hàng \(i\) họ đi ngang qua, người đó sẽ dừng lại, và mua một món hàng để ủng hộ cửa hàng \(i\) đấy nếu còn đủ tiền trong người. Tức nếu \(c \geq a_{i}\) thì \(c \leftarrow c - a_{i}\). Sau đó họ di chuyển sang cửa hàng tiếp theo và làm tương tự cho tới cuối đường.

Đó là những hoạt động mua thường diễn ra trên một khu phố buôn bán không-quá-sầm-uất.

Hôm nay, khu phố lần lượt diễn ra \(q\) hoạt động, mỗi hoạt động thuộc một trong hai loại sau:

• Hoạt động loại \(1\) là mỗi cửa hàng từ \(1\) tới \(x\) nghe tin vật giá tăng \(y\).
• Hoạt động loại \(2\) là có một người khách hàng đem theo \(c\) đồng để đi mua sắm, bắt đầu tại cửa hàng \(u\).

Tại mỗi thời điểm có người mua hàng, bạn hãy cho biết họ mua được bao nhiêu món đồ nhé.

Input

• Dòng đầu tiên chứa số nguyên \(n\) \((1 \leq n \leq 3 \times 10^{5})\) là số cửa hàng.
• Dòng tiếp theo chứa \(n\) số nguyên \(a_{1}, a_{2}, \ldots, a_{n}\) \((1 \leq a_{i} \leq 2 \times 10^{13})\) lần lượt là giá của các cửa hàng.
• Dòng tiếp theo chứa số nguyên \(q\) \((1 \leq q \leq 3 \times 10^{5})\) là số hoạt động.
• Trong \(q\) dòng tiếp theo, dòng thứ \(i\) thuộc một trong hai dạng sau:
  • \(1\) \(x\) \(y\): cho biết hoạt động thứ \(i\) là hoạt động loại \(1\), với các tham số \(x\) và \(y\) \((1 \leq x \leq n, 1 \leq y \leq 2 \times 10^{13})\) tương ứng;
  • \(2\) \(u\) \(c\), cho biết hoạt động thứ \(i\) là hoạt động loại \(2\), với các tham số \(u\) và \(c\) \((1 \leq u \leq n, 1 \leq c \leq 2 \times 10^{13})\) tương ứng.

Output

• Với mỗi truy vấn loại \(2\), in ra một số nguyên duy nhất trên một dòng là số lượng món hàng mà người này mua được.

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 5000\).
• Subtask \(2\) (\(20\%\) số điểm): \(a_{i}\) và \(y\) đều là lũy thừa cơ số \(2\) (số có dạng \(2^{k}\) với \(k\) là một số nguyên không âm) với mọi \(i\) thỏa mãn \(1\leq i \leq q\) và mọi \(y\) trong các hoạt động loại \(1\).
• Subtask \(3\) (\(15\%\) số điểm): Không có hoạt động loại \(1\).
• Subtask \(4\) (\(15\%\) số điểm): Các hoạt động loại \(1\) nằm trước các hoạt động loại \(2\).
• Subtask \(5\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.

Example

8
1919 1650 1496 849 674 565 98 20
9
2 6 2356
1 1 236
1 7 1122
2 7 4086
2 5 6863
1 8 1532
1 8 825
1 2 1890
2 1 10000

3
2
4
6

Loại xe điện Alset mới được nghiên cứu bởi giáo sư Q của trường đại học LQD được đánh giá cao trong giới chuyên môn, và sẽ sớm được đưa ra thị trường. Nhằm đánh giá kĩ hơn các đặc tính của xe, các nhà đầu tư muốn theo dõi giáo sư Y mô phỏng quá trình vận hành của nó.
Trong điều kiện mô phỏng, bản đồ thành phố được đơn giản hóa thành lưới ô vuông vô tận. Ta gắn vào bản đồ này một hệ trục tọa độ Oxy. Giả sử có giao lộ nằm tại mọi điểm có tọa độ nguyên của mặt phẳng; và với mọi giao lộ \((x, y)\), luôn có con đường nối:

• Giao lộ tại \((x, y)\) với giao lộ tại \((x, y + 1)\).
• Giao lộ tại \((x, y)\) với giao lộ tại \((x + 1, y)\).

Xe điện Alset chỉ có thể đi dọc theo các con đường, đi từ một giao lộ này tới giao lộ khác liền kề nó. Trong một đơn vị thời gian, sử dụng một đơn vị năng lượng tiêu chuẩn, xe có thể đi từ giao lộ \((x, y)\) tới giao lộ \((u, v)\) nếu \(|x - u| + |y - v| = 1\).

Người ta cũng bố trí \(n\) trạm sạc đặc biệt, trạm thứ \(i\) ở tại giao lộ \((x_{i}, y_{i})\). Mỗi khi dừng tại một trong những trạm này, xe sẽ được nạp đầy năng lượng, bằng với dung tích \(w\) của nó.

Trong mô phỏng này, có \(q\) thử thách được đặt ra. Thử thách thứ \(j\) giả sử rằng nếu xe bắt đầu tại trạm sạc thứ \(s_{j}\), để đi tới được trạm thứ \(t_{j}\), thì dung tích \(w\) của nó nhỏ nhất có thể bằng bao nhiêu? (trong quá trình di chuyển có thể đi qua các trạm sạc khác tùy ý).

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(q\) \((1 \leq n, q \leq 2 \cdot 10^{5})\) lần lượt là số trạm sạc và số thử thách.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(x_{i}\) và \(y_{i}\) \((|x_{i}|, |y_{i}| \leq 10^{9})\) là vị trí của trạm sạc thứ \(i\).
• Trong \(q\) dòng tiếp theo, dòng thứ \(j\) chứa hai số nguyên \(s_{j}\) và \(t_{j}\) \((1 \leq s_{j}, t_{j} \leq n)\) mô tả một thử thách thứ \(j\).

Output

• Gồm \(q\) dòng, dòng thứ \(j\) chứa đáp án của thử thách thứ \(j\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n, q \leq 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n, q \leq 1000\).
• Subtask \(3\) (\(20\%\) số điểm): \(x_{i} = 0\) với mọi \(1 \leq i \leq n\).
• Subtask \(4\) (\(20\%\) số điểm): \(0 \leq x_{i} \leq 1\) với mọi \(1 \leq i \leq n\).
• Subtask \(5\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

5 3
0 0
0 0
3 3
1 2
6 8
1 2
2 3
1 5

0
3
8