Vì dinhquan có chấp niệm với Miền Nam, cộng với việc anh ấy có vấn đề về hô hấp nên anh ấy chọn học đại học ở TP HCM. min và truyenpham là 2 người em của anh ấy, cũng có vấn đề về hô hấp nên cũng chọn học đại học ở TP HCM, năm nay là năm đầu tiên 2 bạn rời xa nhà để học đại học. dinhquan là một bậc tiền bối tốt bụng nên sau khi 2 người em của anh ấy đến, anh ấy cùng kinh nghiệm 1 năm sống ở TP HCM dẫn min và truyenpham du ngoạn thành phố. Sau khi đi chơi xong xuôi xong, dinhquan liền dẫn 2 người em của một đến một con đường....
Con đường bida vừa được khai trương, là một điểm đến vô cùng hấp dẫn với những bạn trẻ có đam mê chọc bi. Có \(n\) quán bida nằm trên các số nhà liên tiếp \(1, 2, 3..,n\) của con đường bida. Bằng kiến thức của mình, dinhquan biết được tổng cộng \(m\) cách chơi bida, cậu đánh số chúng từ \(1\) đến \(m\). Theo quảng cáo, cậu cũng biết mỗi địa điểm \(i\) chỉ chuyên một loại là \(a_i\).
dinhquan là một con nghiện chọc chính hiệu nên anh ấy đã dụ dỗ 2 người em min và truyenpham của mình vào bộ môn này, anh ấy và 2 người em sẽ chơi ở một vài địa điểm liên tiếp nhau, từ số nhà \(l\) đến số nhà \(r\). dinhquan đánh giá một kế hoạch \((l, r)\) như sau:
- Giả sử sau khi chơi toàn bộ cách chơi từ địa điểm thứ \(l\) tới \(r\), có \(k\) cách chơi chưa chơi được, lần lượt là \(c_1, c_2, c_3,...,c_k\).
- Độ thèm thuồng sẽ bằng với \(c_1 + c_2 + c_3 + .... + c_k\).
Để chắc chắn 2 người em của mình sẽ thực sự nghiện, dinhquan cần tính tổng độ thèm thuồng của toàn bộ kế hoạch \((l, r)\) với \(1 \leq l \leq r \leq n\) (nói cách khác là đoạn các quán bida liên tiếp) vì anh sẽ cho 2 người em của mình chơi hết tất cả các đoạn \((l, r)\) trong \(n\) quán.
dinhquan và 2 người em của mình đang say mê với bộ môn này. Nên việc tính toán đành giao cho bạn :(
Yêu cầu: cho trước \(n,m,a\). Hãy tính tổng độ thèm thuồng theo yêu cầu ở trên.
INPUT
- Dòng đầu tiên chứa 2 số nguyên \(n\) và \(m\) \((1 \leq n \leq 2*10^5, 1 \leq m \leq 10^9)\) lần lượt là số địa điểm và số cách chơi bida.
- Dòng thứ hai chứa \(n\) số \(a_1, a_2, ..., a_n\) \((1 \leq a_i \leq m)\) là cách chơi duy nhất mà quán đó có.
- Lưu ý rằng có thể có các quán khác nhau cùng có một cách, hoặc có cách không có quán nào có.
OUPUT
- In ra tổng độ thèm thuồng của mọi đoạn đường liên tiếp. Vì kết quả có thể rất lớn, hãy in ra sau khi lấy dư cho 2310200779.
SUBTASK
- Subtask 1 (\(20\)%): \(1 \leq n,m \leq 500\).
- Subtask 2 (\(30\)%) : \(1 \leq n,m \leq 5000\).
- Subtask 3 (\(50\)%) : không có giới hạn gì thêm
Example
| Input | Output |
|---|---|
| 3 4 1 2 3 |
40 |
| 8 4 2 3 1 2 4 3 1 3 |
124 |
| 8 1000000000 123456789 20040105 22071997 30081945 19051890 19450205 19800209 1969 |
1516368163 |
Giải thích Test 1 :
- \([1,1]\) : không mua được các loại \(2,3,4\), độ thèm thuồng là \(9\).
- \([1,2]\) : không mua được các loại \(3,4\), độ thèm thuồng là \(7\).
- \([1,3]\) : không mua được loại \(4\), độ thèm thuồng là \(4\).
- \([2,2]\) : không mua được các loại \(1,3,4\), độ thèm thuồng là \(8\).
- \([2,3]\) : không mua được các loại \(1,4\), độ thèm thuồng là \(5\).
- \([3,3]\) : không mua được các loại \(1,2,4\), độ thèm thuồng là \(7\).
Vậy tổng độ thèm thuồng là 40
Nguồn : LQDOJ
bài 2