Nhét bi vào quần

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Pikachu là một cao thủ chơi bi. Pikachu có n cái quần và để chuẩn bị cho mọi lời thách đấu của mấy con gà, anh luôn nhét sẵn một số lượng bi trong quần của mình. Ban đầu không có quần nào có bi. Mỗi lần muốn chọn cái quần thứ i để mặc, anh sẽ đi từ cái quần thứ nhất đến cái quần thứ i, lấy tất cả số bi trong các cái quần đó và mặc cái quần thứ i vào. Là một người ngăn nắp, sau khi giặt xong cái quần vừa mặc, anh sẽ nhét lại quần vào móc và nhét lại các viên bi như cũ. Mỗi lần thắng một trận đấu bi, anh sẽ được thêm x viên bi và anh sẽ chọn một cái quần p nào đó để nhét số bi đó vào. Vì lười tính, hãy đếm số bi mà anh ấy có khi lấy một cái quần.

Nói cho dễ hiểu, cho một mảng an phần tử (n105) đều có giá trị là 0. Có q truy vấn (q105) thuộc một trong hai loại sau:

  • 1px: tăng giá trị ap thêm x đơn vị.
  • 2i: tính tổng các phần tử a1,a2,...,ai.

Input

  • Dòng đầu chứa số 2 nguyên n,q (n,q105).
  • q dòng tiếp theo chứa q truy vấn thuộc một trong hai loại trên.

Tất cả các số trong input đều dương và không quá 109.

Output

  • Kết quả của các truy vấn loại 2 theo thứ tự.

Sample Input 1:

Copy
5 5
1 2 2
2 3
1 1 4
1 4 6
2 5

Sample Output 1:

Copy
2
12

Nhét bi vào nhiều quần

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Pikachu là một cao thủ chơi bi. Pikachu có n cái quần và để chuẩn bị cho mọi lời thách đấu của mấy con gà, anh luôn nhét sẵn một số lượng bi trong quần của mình. Ban đầu không có quần nào có bi. Mỗi lần muốn chọn cái quần thứ i để mặc, anh sẽ mặc cái quần thứ i vào và lấy hết số bi trong quần đấy. Là một người ngăn nắp, sau khi giặt xong cái quần vừa mặc, anh sẽ nhét lại quần vào móc và nhét lại các viên bi như cũ. Mỗi lần thắng một trận đấu bi, anh sẽ được thêm một số viên bi và anh sẽ nhét x viên bi vào các quần từ l đến r (lr). Vì lười tính, hãy đếm số bi mà anh ấy có khi lấy một cái quần.

Nói cho dễ hiểu, cho một mảng an phần tử (n105) đều có giá trị là 0. Có q truy vấn (q105) thuộc một trong hai loại sau:

  • 1lrx: tăng giá trị al,al+1,...,ar thêm x đơn vị.
  • 2i: đưa ra giá trị của phần tử ai.

Input

  • Dòng đầu chứa số 2 nguyên n,q (n,q105).
  • q dòng tiếp theo chứa q truy vấn thuộc một trong hai loại trên.

Tất cả các số trong input đều dương và không quá 109.

Output

  • Kết quả của các truy vấn loại 2 theo thứ tự.

Sample Input 1:

Copy
4 5
1 2 3 5
2 3
1 1 4 7
2 3
2 4

Sample Output 1:

Copy
5
12
7

Nghịch Thế

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho một dãy số a1,a2,...aN. Một nghịch thế là một cặp số u,v sao cho u<vau>av. Nhiệm vụ của bạn là đếm số nghịch thế.

Input

  • Dòng đầu ghi số nguyên dương N (N105).
  • Dòng sau gồm N số nguyên dương ai (1ai105).

Output

  • In ra kết quả của bài toán.

Subtasks

  • Subtask 1: n5000. (50%)
  • Subtask 2: Không giới hạn gì thêm.

Sample Input 1

Copy
3
3 1 2
Sample Output 1
Copy
2

Dãy con tăng

Nộp bài
Time limit: 30.0 / Memory limit: 256M

Point: 100

Cho mảng a gồm n phần tử. Hãy đưa ra độ dài dãy con tăng dài nhất của mảng và số dãy con tăng có độ dài như thế lấy dư cho 109+7.

Input

  • Dòng đầu chứa số nguyên dương n (n105).
  • Dòng thứ hai gồm n số nguyên là các phần tử của mảng a.

Tất cả các số trong input đều có giá trị tuyệt đối không quá 109.

Output

  • Gồm 2 số nguyên là kết quả của bài toán.

Sample Input 1:

Copy
7
1 1 2 2 4 3 3

Sample Output 1:

Copy
3 12

Nghịch thế 2

Nộp bài
Time limit: 1.0 / Memory limit: 256M

Point: 100

Cho mảng a gồm n phần tử. Dãy nghịch thế độ dài k là dãy các chỉ số i1,i2,,...,ik sao cho i1<i2<...<ikai1>ai2>...>aik. Hãy đưa ra số lượng dãy nghịch thế độ dài k lấy dư cho 109.

Input

  • Dòng đầu chứa 2 số nguyên dương n,k (n104,k10).
  • Dòng thứ hai gồm n số nguyên là các phần tử của mảng a.

Tất cả các số trong input đều có giá trị tuyệt đối không quá 109.

Output

  • Gồm 1 số nguyên là kết quả của bài toán.

Sample Input 1:

Copy
3 2
3 2 1

Sample Output 1:

Copy
3