BIT / Fenwick tree

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Cho \(Q\) thao tác thực hiện lần lượt, thao tác thứ \(i\) sẽ có một trong hai loại như sau:

• \(1\) \(p_i\) \(x_i\): Tăng phần tử ở vị trí \(p_i\) lên \(x_i\) đơn vị.
• \(2\) \(u_i\) \(v_i\): Tính tổng các phần tử từ vị trí \(u_i\) tới vị trí \(v_i\).

Yêu cầu
Thực hiện tất cả lần lượt \(Q\) thao tác, và in ra kết quả của thao tác loại \(2\).

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) \((A_i \leq 10^9)\).
• \(Q\) dòng tiếp theo, với dòng thứ \(i\): số đầu tiên trên dòng là \(1\) hoặc \(2\). Số \(1\) theo sau bởi hai số nguyên dương \(p_i\) và \(x_i\) \((1 \leq p_i \leq N\), \(1 \leq x_i \leq 10^4)\). Số \(2\) theo sau bởi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \leq u_i \leq v_i \leq N)\).

Output

• Với thao tác loại \(2\) có dạng \(2\) \(u\) \(v\), in ra tổng các phần atử từ vị trí \(u\) tới vị trí \(v\) trên một dòng.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \leq 10^3\), \(Q \leq 10^3\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \leq 10^5\), \(Q \leq 10^5\).

Example

6 5
9 2 4 7 4 8
1 5 6
2 1 5
1 3 8
1 2 3
2 2 4 

32
24

Cho một mảng gồm \(N\) phần tử \(a[1],a[2],...,a[N]\) và có \(T\) truy vấn có dạng như sau:

• \(1\text{ }l\text{ }r\): In ra tổng tất cả các phần tử thuộc đoạn \([l,r]\)
• \(2\text{ }x\text{ }y\): Thay giá trị tại vị trí thứ \(x\) thành \(y\) (tức là gán \(a[x]=y\))

Input

• Dòng thứ nhất chứa hai số nguyên \(N,T\)
• Dòng thứ hai chứa \(N\) số nguyên \(a[1],a[2],...,a[N]\) \((1\leq a_i\leq 10^5)\)
• \(T\) dòng tiếp theo chứa \(T\) truy vấn: \(1 \text{ }l\text{ }r\) \((1\leq l\leq r\leq n)\) hoặc \(2\text{ }x\text{ }y\) \((1\leq x\leq N, 1\leq y\leq 10^4)\)

Output

• Ứng với mỗi truy vấn \(1\text{ }l\text{ }r\) in ra tổng cần tìm

Constraints

• \(1\le N\le 10^4\)
• \(1\le T\le 10^5\)

Example

5 3
1 2 3 4 5
1 2 3
2 2 3
1 2 3 

5
6

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là xử lí \(q\) truy vấn của các loại sau đây:

1. tăng mỗi giá trị trong đoạn \([a,b]\) thêm \(u\)
2. giá trị ở vị trí \(k\) là gì?

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(q\): số lượng giá trị và truy vấn
• Dòng thứ hai có \(n\) số nguyên \(x_1, x_2,\ldots, x_n\): các giá trị của dãy
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có ba số nguyên: hoặc "1 \(a\) \(b\) \(u\)" hoặc "2 \(k\)"

Constraints

• \(1 \leq n,q \leq 2\cdot 10^5\)
• \(1 \leq x_i,u \leq 10^9\)
• \(1 \leq k \leq n\)
• \(1 \leq a \leq b \leq n\)

Output

• In ra kết quả của mỗi truy vấn loại 2

Example

8 3
3 2 4 5 1 1 5 3
2 4
1 2 5 1
2 4

5
6

Có \(n\) hộp kẹo, hộp thứ \(i\) có \(a_i\) viên và tất cả \(m\) người lần lượt tới ăn. Người thứ \(i\) sẽ chỉ ăn kẹo ở các hộp có số lượng còn lại không ít hơn \(t_i\) chiếc và sẽ ăn ở những hộp này, mỗi hộp một viên.

Yêu cầu: Hãy xác định số kẹo từng người đã ăn.

Input

• Dòng đầu tiên chứa số nguyên dương \(n\) (\(n\le 10^5\)),
• Dòng thứ 2 chứa \(n\) số nguyên dương \(a_1,a_2,…,a_n\) (\(a_i\le 10^9\))
• Dòng thứ 3 chứa số nguyên dương \(m\) (\(m\le 10^5\)),
• Dòng thứ 4 chứa \(m\) số nguyên dương \(t_1,t_2,…,t_M\) (\(t_i\le 10^9\)),

Output

• Đưa ra m số nguyên, mỗi số trên một dòng. Số thứ \(i\) là số viên kẹo người thứ \(i\) đã ăn.

Example

3
3 1 1
2
1 2

3
1

Cho mảng \(n\) số \(a\). Một nghịch thế trong mảng là một cặp số \(i\), \(j\) thỏa mãn \(i < j\) và \(a_{i} > a_{j}\). Hãy đếm số cặp nghịch thế \((i,j)\) của mảng.

Input

Gồm hai dòng:

• Dòng đầu tiên chứa duy nhất một số nguyên dương \(n\) số phần tử của mảng \((1 \le n \le 10^{5})\).
• Dòng thứ hai chứa số \(n\) nguyên là các phần tử của mảng \(a\) \((1 \le a_{i} \le 10^{5})\).

Output

• In ra trên một dòng số nguyên duy nhất là số cặp nghịch thế của dãy.

Example

5
2 1 1 2 3

2

Cho \(n\) là một số nguyên dương và \(x = (x_1, x_2, ..., x_n)\) là một hoán vị của dãy số \((1, 2, ..., n)\). Với \(\forall i: 1 \le i \le n\), gọi \(t_i\) là số phần tử đứng trước giá trị \(i\) mà lớn hơn \(i\) trong dãy \(x\). Khi đó dãy \(t = (t_1, t_2,..., t_n)\) được gọi là dãy nghịch thế của \(x = (x_1, x_2, ..., x_n)\)

Ví dụ: Với \(n = 6\)

Dãy \(x = (3, 2, 1, 6, 4, 5)\) thì dãy nghịch thế của nó là \(t = (2, 1, 0, 1, 1, 0)\)

Dãy \(x = (1, 2, 3, 4, 5, 6)\) thì dãy nghịch thế của nó là \(t = (0, 0, 0, 0, 0, 0)\)

Dãy \(x = (6, 5, 4, 3, 2, 1)\) thì dãy nghịch thế của nó là \(t = (5, 4, 3, 2, 1, 0)\)

Input

Vào từ file văn bản IVECTOR.INP gồm:

• Dòng 1: Chứa số nguyên dương \(n \le 10^5\)
• Dòng 2: Chứa dãy hoán vị \(x\) gồm \(n\) số \(x_1, x_2, ..., x_n\)
• Dòng 3: Chứa dãy nghịch thế \(t\): gồm \(n\) số \(t_1, t_2,..., t_n\)

Output

Ghi ra file văn bản IVECTOR.OUT gồm:

• Dòng 1: Ghi lần lượt từng phần tử của dãy nghịch thế của \(x\)
• Dòng 2: Ghi lần lượt từng phần tử của dãy hoán vị của \(t\)

Example

6
1 2 3 4 5 6
2 1 0 1 1 0

0 0 0 0 0 0
3 2 1 6 4 5

Cho một dãy số nguyên gồm \(N\) phần tử \(A[1],A[2],\cdots A[N]\).

Biết rằng dãy con tăng đơn điệu là 1 dãy \(A[i_1],\cdots A[i_k]\) thỏa mãn \(i_1<i_2< \cdots <i_k\) và \(A[i_1]<A[i_2]< \cdots <A[i_k]\).

Yêu cầu: Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phần tử.

Input

• Dòng đầu tiên chứa số nguyên dương \(N (1 \leq N \leq 30000)\)
• Dòng thứ 2 ghi \(N\) số nguyên \(A[1],A[2],\cdots ,A[N](0 \leq A[i] \leq 1000000)\).

Output

• Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Example

6
1 2 5 4 6 2 

4

Trong một cuộc thi thả diều, ban giám khảo căn cứ vào độ cao của mỗi chiếc diều đạt được khii thả lên trời và xếp hạng cho chiếc diều đó theo một cách đặc biệt: Những chiếc diều không được thả cùng một lúc, mà theo trình tự từng chiệc một. Khi một chiếc diều được thả lên trời, ban giám khảo sẽ căn cứ vào độ cao của chiếc diều và xếp hạng cho chiếc diều đó bằng cách so độ cao của nó với độ cao của những chiếc diều đã thả trước đó. Ví dụ, giả sử độ cao của sáu chiếc diều theo thứ tự được thả như sau:
\(\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (78,24,68,40,39,89)\)

Chiếc đầu tiên xếp hạng \(1\) vì trước nó chưa có chiếc diều nào được thả. Chiếc thứ hai xếp hạng \(2\) vì \(24 < 78\). Chiếc thứ ba cũng xếp hạng \(2\) vì \(24 < 68 < 78\). Chiếc thứ tư xếp hạng \(3\) vì \(24 < 40 < 68 < 78\), chiếc thứ năm xếp hạng \(4\) vì \(24 < 39 < 40 < 68 < 78\) và chiếc cuối cùng xếp hạng nhất với độ cao \(89\) và \(24 < 39 < 40 < 68 < 78 < 89\). Như vậy trình tự dãy số xếp hạng được công bố sẽ là: \((1,2,2,3,4,1)\). Tóm lại hạng của một chiếc diều bằng số diều đã thả cao hơn nó cộng thêm \(1\).

Yêu cầu:

• Có \(n\) chiếc diều lần lượt được thả lên trời, em hãy cho biết dãy số biểu diễn giá trị xếp hạng của \(n\) chiếc diều.

Input

• Dòng đầu một số nguyên \(n \le 10^5\) cho biết số chiếc diều tham gia dự thi.
• \(n\) dòng tiếp theo, mỗi dòng ghi một số nguyên dương \(\le 10^9\) mô tả độ cao của một chiếc diều, theo thứ tự mà nó được thả lên.

Output

• Gồm \(n\) dòng: dòng thứ \(i\) ghi số nguyên biểu diễn giá trị xếp hạng của chiếc diều thứ \(i\) tại thời điểm nó được thả lên.

Example

6
78
24
68
40
39
89

1
2
2
3
4
1

Có \(n\) con ma lần lượt gia nhập nghĩa trang theo thứ tự là \(1, 2, 3,..., n\). Chỉ số sức mạnh của các con ma tương ứng là \(a_1, a_2,..., a_n\). Khi một con ma mới gia nhập nghĩa trang thì nó sẽ bị các con ma cũ bắt nạt. Giả sử con ma mới có chỉ số sức mạnh là \(M\) và con ma cũ có chỉ số sức mạnh là \(C\), nếu \(M < C\) thì con ma mới phải nộp cho con ma cũ \(C - M\) đồng tiền vàng. Nếu \(M \ge C\) thì thôi. Bạn hãy tính thử xem sau khi đủ \(n\) con ma gia nhập nghĩa trang thì các con ma phải đưa lẫn nhau tổng cộng bao nhiêu đồng tiền vàng?.

Input

• Dòng thứ nhất là số nguyên \(n\ (1 \le n \le 10^5)\)
• Dòng thứ hai là \(n\) số nguyên \(a_1, a_2, ..., a_n\), mỗi số cách nhau một khoảng trắng \((1 \le a_i \le 10^9)\)

Output

• Là số nguyên xác định tổng cộng số đồng tiền vàng các con ma đưa lẫn nhau. Chỉ cần in ra \(9\) chữ số cuối \((\mod\ 10^9)\)

Example

4
3 2 4 1

7

Nhân ngày lễ tình nhân, Ami quyết định đi leo núi. Ami đứng trước \(n\) ngọn núi được đánh số từ 1 đến \(n\), mỗi ngọn núi có chiều cao là \(h_i\) và một chỉ số boosting là \(d_i\). Ami có thể bắt đầu leo núi ở bất kì ngọn núi nào và khi vượt qua ngọn núi \(i\), Ami có thể dừng lại hoặc phải leo ở những ngọn núi có chỉ số lớn hơn \(i\) và có độ cao lớn hơn độ cao ngọn núi hiện tại ít nhất là \(d_i\). Hệ thức hóa, giả sử Ami đang ở ngọn núi \(i\) có chiều cao \(h_i\) và chỉ số boosting \(d_i\), Ami sẽ được leo ngọn núi \(j\) nếu \(j > i\) và \(h_j – h_i \ge d_i\). Ami muốn leo nhiều núi nhất có thể, do đó các bạn được phép giúp Ami tìm ra lịch trình leo núi tối ưu.

Input

• Dòng đầu tiên là một số nguyên dương \(n\ (n \le 2 \times 10^5)\) là số ngọn núi
• Dòng tiếp theo là \(n\) số nguyên dương \(h_i\ (h_i \le 10^6)\) là độ cao ngọn núi thứ \(i\).
• Dòng cuối cùng là \(n\) số nguyên dương \(d_i\ (d_i \le 10^6)\) là chỉ số boosting của ngọn núi \(i\).

Output

• Một số nguyên là số ngọn núi nhiều nhất Ami có thể leo.

Example

5
1 2 3 4 5
2 1 3 1 1

3

1
1
1

1