Đội quân Pokémon

Điểm: 7,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho dãy số nguyên đôi một phân biệt $a_{1}, a_{2}, \dots, a_{n}$ .

Với mọi dãy con (không nhất thiết liên tiếp, không rỗng) $a_{b_{1}}, a_{b_{2}}, \dots, a_{b_{k}}$ với $1 \leq b_{1} < b_{2} < \dots < b_{k} \leq n$ , ta định nghĩa độ mạnh của dãy con đó là tổng đan dấu:

$a_{b_{1}} - a_{b_{2}} + a_{b_{3}} - a_{b_{4}} + \dots$

Bạn cần tìm độ mạnh lớn nhất có thể của một dãy con bất kỳ.

Sau đó có $q$ truy vấn. Mỗi truy vấn cho hai chỉ số $l$ và $r$ — hãy hoán đổi $a_{l}$ và $a_{r}$ , rồi in lại độ mạnh lớn nhất.

Dữ liệu vào

Dòng đầu chứa số nguyên dương $t$ — số bộ test.

Với mỗi bộ test:

Dòng đầu chứa hai số $n$ và $q$ .
Dòng thứ hai chứa $n$ số nguyên phân biệt $a_{1}, a_{2}, \dots, a_{n}$ ( $1 \leq a_{i} \leq n$ ).
$q$ dòng tiếp theo, mỗi dòng chứa hai số $l_{i}$ và $r_{i}$ ( $1 \leq l_{i} \leq r_{i} \leq n$ ).

Dữ liệu ra

Với mỗi bộ test, in ra $q + 1$ số nguyên: độ mạnh lớn nhất trước khi có thao tác hoán đổi, và sau mỗi thao tác hoán đổi.

Ràng buộc

$1 \leq t \leq 10^{3}$
$1 \leq n \leq 3 \cdot 10^{5}$
$0 \leq q \leq 3 \cdot 10^{5}$
$1 \leq a_{i} \leq n$ và các $a_{i}$ đôi một phân biệt trong mỗi bộ test.
Tổng $n$ trên tất cả bộ test không vượt quá $3 \cdot 10^{5}$ .
Tổng $q$ trên tất cả bộ test không vượt quá $3 \cdot 10^{5}$ .

Ví dụ

Input	Output	Giải thích
3 3 1 1 3 2 1 2 2 2 1 2 1 2 1 2 7 5 1 2 5 4 3 6 7 1 2 6 7 3 4 1 2 2 3	3 4 2 2 2 9 10 10 10 9 11	Bộ 1: dãy $[1, 3, 2]$ cho độ mạnh $3$ ; sau khi đổi $a_{1}$ và $a_{2}$ thì dãy là $[3, 1, 2]$ , chọn dãy con $3, 1, 2$ cho $3 - 1 + 2 = 4$ . Bộ 3: ban đầu chọn $5 - 3 + 7 = 9$ ; sau thao tác cuối, dãy là $[1, 4, 2, 5, 3, 7, 6]$ , chọn $4 - 2 + 5 - 3 + 7 = 11$ .
1 4 2 4 1 3 2 1 4 2 3	6 5 6	Ban đầu $a = [4, 1, 3, 2]$ , chọn $4 - 1 + 3 = 6$ . Đổi $a_{1}, a_{4}$ ra $[2, 1, 3, 4]$ , độ mạnh tốt nhất là $4$ hoặc lấy chỉ phần tử $4$ kết hợp với cực tiểu trước nó — đáp án là $5$ . Đổi tiếp $a_{2}, a_{3}$ ra $[2, 3, 1, 4]$ , chọn $3 - 1 + 4 = 6$ .

Bình luận

Không có bình luận tại thời điểm này.