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

Hãy đọc nội quy trước khi bình luận.


  • 1
    pppssslc  đã bình luận lúc 25, Tháng 6, 2025, 17:15

    My sol:

    • Gọi ~S~ là tổng số lượng cặp nghịch thế.
    • Gọi ~Calc1(X, Y)~ là số lượng chỉ số ~j~ mà ~1 ≤ j < X~ và ~A(j) > X~.
    • Gọi ~Calc2(X, Y)~ là số lượng chỉ số ~j~ mà ~n ≥ j > X~ và ~A(j) > X~.

    Nhận xét:

    • Khi thay đổi ~A(X)~ thành ~Y~ thì số lượng cặp ngịch thế sẽ trừ đi số cặp nghịch thế ~(i, j)~ mà ~i = X~ hoặc ~j = X~ cộng với số cặp nghịch thế ~(i, j)~ mà ~i = X~ hoặc ~j = X~ nếu ~A(x)~ là ~Y~.
    • Hay ta có công thức: ~S = S - Calc1(X, A(x)) - Calc2(X, A(X)) + Calc1(X, Y) + Calc2(X, Y)~

    BIT + chia căn:

    • Ta chia mảng thành ~\sqrt{n}~ block, mỗi block dùng 1 cây BIT để quản lí số lượng phần tử theo các giá trị.
    • Dùng 1 cây BIT để quản lí các block.

    Độ phức tạp: ~O(log_2(\sqrt{n}) × log_2(5 × 10 ^ 4))~


  • 1
    TranThienPhuc2657  đã bình luận lúc 9, Tháng 6, 2025, 9:22

    Bài tương tự: https://oj.vnoi.info/problem/thswaps