Inversion Counting
Xem dạng PDF
Gửi bài giải
Điểm:
0,70 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
512M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho dãy ~A~ gồm ~N~ phần tử nguyên dương. Có ~M~ thao tác được thực hiện trên dãy ~A~ có dạng như sau:
- ~X~ ~Y~: Gán ~A_X = Y~, rồi đếm số lượng cặp số nghịch thế tồn tại trong dãy ~A~.
Nhắc lại: Một cặp số nghịch thế trong dãy ~A~ được định nghĩa là một cặp số nguyên ~(i, j)~ sao cho ~1 \leq i < j \leq n~ và ~A_i > A_j~.
Input
- Dòng đầu chứa số nguyên dương ~N~ (~1 \leq N \leq 250000~).
- Dòng thứ ~2~ chứa ~N~ số nguyên dương ~A_i~ cách nhau bởi dấu cách (~A_i \leq 5 \times 10^4~).
- Dòng thứ ~3~ chứa số nguyên dương ~M~ (~M \leq 10^4~).
- ~M~ dòng tiếp theo, mỗi dòng chứa ~2~ số nguyên dương ~X, Y~ (~X \leq N~ và ~Y \leq 5 \times 10^4~).
Output
Xuất ra ~M~ dòng, dòng thứ ~i~ chứa ~1~ số nguyên duy nhất là đáp án cho truy vấn thứ ~i~.
Sample Input
10
2 6 6 4 7 6 3 5 9 1
7
8 8
5 1
5 6
10 5
7 1
10 10
4 6
Sample Output
17
18
16
13
14
8
6
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bài tương tự: https://oj.vnoi.info/problem/thswaps