Đếm nghịch thế

View as PDF
Submit solution
Points: 0.22 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem type
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 9
    pppssslc  commented on June 25, 2025, 5:14 p.m. ← edited

    My sol:

    Nhận xét:

    Sau mỗi truy vấn, số lượng cặp nghịch thế sẽ:

    • Giảm đi: số lượng ~y~(~y < X~) mà ~A(y) > A(X)~ và ~z~(~z > X~) mà ~A(z) < A(X)~.
    • Tăng lên: số lượng ~y~(~y < x~) mà ~A(y) > Y~ và ~z~(~z > X~) mà ~A(z) < 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ị.
    • Có thể dùng thêm 1 cây BIT để quản lí các block giúp tối ưu hơn.

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


  • 5
    TranThienPhuc2657  commented on June 9, 2025, 9:23 a.m.

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


  • -7
    chunguyen2k8  commented on Aug. 2, 2024, 12:26 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -1
    nguyentrieuvy  commented on June 16, 2024, 1:36 a.m.

    cao nhân nào gợi ý cách làm với ạ


  • -4
    hung01062003  commented on Oct. 28, 2022, 3:32 p.m.

    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