Cấu trúc dữ liệu dạng Cây (Segment Tree) - Buổi 2

Có \(n\) khách sạn trên một con đường. Với mỗi khách sạn bạn biết được số phòng còn trống. Nhiệm vụ của bạn là chỉ định các phòng khách sạn cho \(m\) nhóm khách du lịch. Tất cả các thành viên trong cùng một nhóm muốn trọ chung một khách sạn.

Các nhóm sẽ lần lượt đến và bạn biết số phòng yêu cầu của mỗi nhóm. Với mỗi nhóm, bạn luôn tìm khách sạn đầu tiên mà đủ số phòng trống và chỉ định nhóm đấy vào phòng này. Sau đó, số phòng trống của khách sạn này sẽ giảm đi.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(n\), \(m\): Số khách sạn và số nhóm. Các khách sạn được đánh số theo thứ tự từ \(1\) tới \(n\)
• Dòng thứ hai gồm \(n\) số nguyên dương \(h_1,h_2,...,h_n\): số phòng trống của mỗi khách sạn
• Dòng cuối cùng gồm \(m\) số nguyên dương \(r_1,r_2,...,r_m\): số phòng trống mà mỗi nhóm yêu cầu

Constraints

• \(1 \leq n,m \leq 2\cdot 10^5\)
• \(1 \leq h_i \leq 10^9\)
• \(1 \leq r_i \leq 10^9\)

Output

• In ra \(m\) số nguyên là chỉ số của khách sạn được phân cho mỗi nhóm. Nếu nhóm nào đó không được chỉ định vào khách sạn (do không tìm được), in ra số \(0\)

Example

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

3 5 0 1 1

Một công ty có \(N\) nhân viên với với mức lương nhất định. Nhiệm vụ của bạn là theo dõi mức lương và thực hiện truy vấn.

Input

• Dòng thứ nhất gồm hai số nguyên dương \(N, Q\) là số nhân viên và số truy vấn. Các nhân viên được đánh số từ \(1\) tới \(N\).
• Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, ..., A_N\) là lương của mỗi người.
• \(Q\) dòng tiếp theo, mỗi dòng gồm một truy vấn thuộc một trong hai dạng sau:
• \(!\) \(k\) \(x\): thay đổi lương của người thứ \(k\) thành \(x\).
• \(?\) \(a\) \(b\): đếm số người có mức lương từ \(a\) tới \(b\).

Output

• In ra kết quả cho truy vấn \(?\).

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(N, Q \leq 2.10^3\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).
• Subtask \(2\) (\(30\%\) số điểm): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^5\) với \(\forall i, 1 \leq i \leq N\).
• Subtask \(3\) (\(40\%\) số điểm): \(N, Q \leq 2.10^5\), \(1 \leq A_i \leq 10^9\) với \(\forall i, 1 \leq i \leq N\).

Example

5 3
3 7 2 2 5
? 2 3
! 3 6
? 2 3 

3
2

Cho một mảng bao gồm \(N\) số nguyên. Một số phần tử sẽ được cập nhật, và sau mỗi lần cập nhật, nhiệm vụ của bạn là tìm tổng lớn nhất của tất cả các đoạn con (liên tiếp) trong mảng.

Input

• Dòng đầu tiên gồm hai số nguyên dương \(N, Q\): Kích thước của mảng và số truy vấn.
• Dòng thứ hai gồm \(N\) số nguyên \(A_1, A_2, ..., A_N\) \((|A_i| \leq 10^9)\).
• \(Q\) dòng tiếp theo, mỗi dòng có hai số nguyên \(k\) và \(x\) \((1 \leq k \leq N, |x| \leq 10^9)\): thay đổi phần tử \(k\) thành giá trị \(x\).

Output

• Sau mỗi lần cập nhật, in ra tổng lớn nhất của tất cả các đoạn con trong mảng. Các mảng con rỗng (với tổng bằng 0) vẫn được tính.

Scoring

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

Example

5 3
1 2 -3 5 -1
2 6
3 1
2 -2 

9
13
6

Bạn được cho một mảng \(a\) gồm \(n\) phần tử và \(q\) truy vấn. Có 2 loại truy vấn:

• Loại 1: có dạng \(1\) \(a\) \(b\): Tăng phần tử thứ nhất trong đoạn \([a, b]\) lên 1 đơn vị, phần tử thứ 2 lên 2 đơn vị, và cứ thế đến hết.
• Loại 2: có dạng \(2\) \(a\) \(b\): Tính tổng tất cả các phần tử trong đoạn \([a, b]\)

Input

• Dòng thứ nhất gồm 2 số \(n\) và \(q\)
• Dòng thứ 2 gồm \(n\) phần tử của mảng \(a\)
• \(q\) dòng còn lại, mỗi dòng là 1 truy vấn thuộc loại 1 hoặc 2

Constraints

• \(1 \leq n, q \leq 2\cdot 10^5\)
• \(1 \leq a_i \leq 10^6\)
• \(1 \leq a, b \leq n\)

Output

• Với mỗi truy vấn loại 2, in ra tổng của các phần tử trong đoạn \([a, b]\)
• Mỗi đáp án đều được in trên một dòng

Example

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

17
32

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:

1. cập nhập giá trị ở vị trí \(k\) thành \(u\).
2. tổng tiền tố tối đa trong đoạn \([a,b]\) 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,...,x_n\): các giá trị của mảng.
• Cuối cùng, có \(q\) dòng mô tả các truy vấn. Mỗi dòng có ba số nguyên: 1 k u hoặc 2 a b.

Output

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

Constraints

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

Example

8 4
1 2 -1 3 1 -5 1 4
2 2 6
1 4 -2
2 2 6
2 3 4

5
2
0

Có \(n\) tòa nhà trên một con đường, được đánh số \(1,2,..,n\). Mỗi tòa nhà có một tiệm bánh pizza và một căn hộ.

Giá pizza trong tòa nhà thứ \(k\) là \(p_k\). Nếu bạn gọi một bánh pizza từ tòa nhà \(a\) đến \(b\), giá của nó (với giao hàng) là \(p_a + |a - b|\).

Nhiệm vụ của bạn là xử lí 2 dạng truy vấn sau:

1. Giá pizza \(p_k\) của tòa nhà thứ \(k\) đổi thành \(x\).
2. Bạn đang ở tòa nhà thứ \(k\) và muốn gọi một bánh pizza. Giá tối thiểu để gọi là gì?

Input

• Dòng đầu tiên gồm hai số nguyên \(n\) và \(q\): số tòa nhà và số truy vấn.
• Dòng thứ hai gồm \(n\) số nguyên \(p_1, p_2,...,p_n\): giá pizza ban đầu của mỗi tòa nhà.
• Cuối cùng, có \(q\) dòng truy vấn. Mỗi dòng sẽ là 1 k x hoặc 2 k.

Constraints

• \(1 \leq n,q \leq 2\cdot 10^5\)
• \(1 \leq p_i,x \leq 10^9\)
• \(1 \leq k \leq n\)

Output

• In các đáp án của các truy vấn loại 2.

Example

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

5
4