Đếm nghịch thế

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 2.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, 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.


There are no comments at the moment.