Đếm nghịch thế
Xem dạng PDF
Gửi bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
256M
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ử. Các phần tử đánh số từ 1 đến ~N~. Phần tử thứ ~i~ được ký hiệu là ~A(i)~.
Bạn cần thực hiện ~Q~ truy vấn. Với truy vấn thứ ~i~, bạn phải thay đổi giá trị của 1 số trong mảng ~A~ và phải đếm số cặp nghịch thế trong mảng.
1 cặp nghịch thế là 1 cặp ~(i, j)~ thỏa mãn 2 điều kiện sau:
- ~i < j~
- ~A(i) > A(j)~
Ví dụ:
~A = [4, 3, 3, 4]~
Có 2 cặp nghịch thế:
- 1, 2 (đánh số từ 1)
- 1, 3
Input
- Dòng 1: ~N~, với ~1 \le N \le 250,000~.
- Dòng 2: ~N~ số nguyên thể hiện mảng ~A~. ~(1 \le A(i) \le 50,000)~.
- Dòng 3: ~Q~, với ~1 \le Q \le 10,000~.
- ~Q~ dòng tiếp theo, mỗi dòng 2 số ~X~ và ~Y~, thể hiện truy vấn ~A(X) = Y~. ~(1 \le X \le N, 1 \le Y \le 50,000)~.
Output
Với mỗi truy vấn, in ra 1 số duy nhất là số nghịch thế sau khi áp dụng truy vấn đó.
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.
cao nhân nào gợi ý cách làm với ạ
các cao nhân cho hỏi bài này ngoài cách chia căn thì còn cách nào khác k
bit + trie (online)