#1571. RSEQ

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Trùm CUỐI

Đề bài

Cho một dãy gồm số 𝑛 số nguyên không âm 𝑎_1, 𝑎_2, … , 𝑎_𝑛 𝑇 thao tác trên dãy số, thao tác thứ 𝑖 mô tả bằng số nguyên 𝑣_𝑖 , thao tác này sẽ xóa bỏ phần tử ở vị trí 𝑣_𝑖 khỏi dãy, khi đó dãy số có thể bị tách ra làm các đoạn con.

Nhiệm vụ của bạn cần phải tìm đoạn con có tổng các phần tử là lớn nhất sau mỗi thao tác.

Ví dụ, cho dãy gồm 6 số 7, 10, 2, 0, 0, 7 2 thao tác lần lượt xóa phần tử ở vị trí 2 6 .

Thao tác Dãy số sau khi xóa Đoạn có tổng lớn nhất
1 (xóa phần tử 2) 7, -, 2, 0, 0, 7 2, 0, 0, 7 có tổng là 9
2 (xóa phần tử 6) 7, -, 2, 0, 0, - 7 có tổng là 7

Dữ liệu:

  • Dòng đầu chứa hai số nguyên 𝑛, 𝑇\ (𝑛 ≤ 10^5) ;
  • Dòng thứ hai chứa 𝑛 số nguyên 𝑎_1, 𝑎_2, … , 𝑎_𝑛 (0 ≤ 𝑎_𝑖 ≤ 10^9) ;
  • Dòng thứ ba chứa 𝑇 số nguyên phân biệt 𝑣_1, 𝑣_2, … , 𝑣_𝑇\ (1 ≤ 𝑣_𝑖 ≤ 𝑛) ;

Kết quả:

  • Gồm 𝑇 dòng, mỗi dòng chứa một số nguyên là tổng các phần tử là lớn nhất sau mỗi thao tác tương ứng.

Ví dụ:

Dữ liệu:

6 2
7 10 2 0 0 7
2 6

Kết quả:

9
7

Ràng buộc:

  • 50\% số test của bài có 𝑇 ≤ 10^3 ;
  • 50\% số test còn lại của bài có 𝑇 ≤ 10^5 .