TLE-oj Cup Round 12 - Cặp nghịch thế

Điểm: 1600 (thành phần)

Thời gian: 1.0s

Bộ nhớ: 256M

Input: RCNT.inp

Output: RCNT.out

Tác giả:

Sunlight

Dạng bài

Với một dãy số $a_1,a_2,\dots,a_n$ , một cặp số $(i,j)$ được gọi là cặp nghịch thế khi và chỉ khi $1\le i<j\le n$ và $a_i>a_j$

Bạn được cho một dãy số $a$ và $q$ truy vấn, mỗi truy vấn gồm hai số nguyên dương $u,v$ , và bạn cần phải tính toán số cặp nghịch thế của dãy $a$ nếu đổi giá trị của $a_u$ và $a_v$

Input, Output và Subtasks

Input: (RCNT.inp)

Dòng đầu tiên gồm hai số nguyên dương $n,q\ (n,q\le 10^5)$
Dòng thứ hai gồm $n$ số nguyên dương $a_1,a_2,\dots,a_n$ . Dữ liệu đầu vào đảm bảo dãy $a$ là một hoán vị có $n$ phần tử (hay nói cách khác, $a_i\ne a_j$ với mọi cặp $i\ne j$ và $1\le a_i\le n$ )
$q$ dòng tiếp theo, mỗi dòng gồm hai số nguyên dương $u,v$ biểu thị cho một truy vấn

Output: (RCNT.out)

Gồm $q$ dòng, dòng thứ $i$ là kết quả của truy vấn thứ $i$

Subtasks

Subtask 1 ( $25\%$ ): $n\le 50$
Subtask 2 ( $25\%$ ): $n\le 500$
Subtask 3 ( $25\%$ ): $n\le 5000$
Subtask 4 ( $25\%$ ): Không có ràng buộc gì thêm

Sample

Input (RCNT.inp)

Output (RCNT.out)

3
1
5

Note

Ban đầu: $a=(2,3,1,4)$
Truy vấn 1: $a=(2,4,1,3)$ có các cặp nghịch thế $(1,3), (2,3), (2,4)$
Truy vấn 2: $a=(1,3,2,4)$ có cặp nghịch thế $(2,3)$
Truy vấn 3: $a=(4,3,1,2)$ có các cặp nghịch thế $(1,2), (1,3), (1,4), (2,3), (2,4)$

Bình luận

Không có bình luận nào.