Dãy nghịch thế

View as PDF
Submit solution
Points: 0.08 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem source:
IOICamp Marathon 2005-2006
Problem type
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho một dãy số ~a_{1}~.. ~a_{N}~. Một nghịch thế là một cặp số ~u~, ~v~ sao cho ~u < v~ và ~a_{u} > a_{v}~. Nhiệm vụ của bạn là đếm số nghịch thế.

Input

  • Dòng đầu ghi số nguyên dương ~N~.
  • ~N~ dòng sau mỗi dòng ghi một số ~a_{i}~ (~1 \leq i \leq N~).
  • ~1 \leq N \leq 60000~
  • ~1 \leq a_{i} \leq 60000~

Output

  • Ghi trên một dòng số ~M~ duy nhất là số nghịch thế.

Sample Input

3
3
1
2

Sample Output

2

Comments

Please read the guidelines before commenting.


  • 0
    yazz  commented on Dec. 29, 2025, 12:33 a.m.

    bai nay fenwick cung dc nhe


  • 2
    lamdt  commented on Nov. 17, 2025, 3:56 a.m.

    Học segment tree rồi nhưng vẫn không nhìn ra dấu hiệu nhận biết segment tree để giải bài này.


  • 0
    vominhmanh10  commented on Nov. 3, 2025, 3:56 a.m. ← edited

    dựng mảng cộng dồn p ta thấy nếu duyệt ngược tới phần tử thứ i, tổng p[a[i] - 1] sẽ là số nghịch thế ứng với a[i], sau khi đếm xong ta cập nhật cộng 1 vào p[a[i]], duyêt xong là ra kết quả, việc truy vấn p[a[i] - 1] và cập nhật p[a[i]] được thực hiện bằng BIT

    import sys

def add(i, v):
    while i <= d:
        bit[i] += v
        i += i & -i
def query(i):
    s = 0
    while i > 0:
        s += bit[i]
        i -= i & -i
    return s

sys.setrecursionlimit(10**7)
data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1:]))
d = max(a)
bit = [0] * (d + 1)
res = 0
for i in range(n - 1, -1, -1):
    res += query(a[i] - 1)
    add(a[i], 1)
print(res)

  • -1
    drikbest10  commented on Aug. 12, 2025, 4:13 a.m. ← edit 2

    thật ra segment tree là ngon luôn


  • -7
    HeroMinhSteve  commented on May 28, 2025, 10:22 a.m.

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


    • -3
      nkimletuan  commented on June 16, 2025, 10:28 a.m.

      pro qua a


  • 1
    Free_De_La_Zenith  commented on March 1, 2025, 3:41 p.m.

    seg+lazy


  • -7
    minhtuanvp2011  commented on Oct. 22, 2024, 12:32 p.m.

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


  • -14
    phamducminh538  commented on Aug. 12, 2024, 6:54 a.m. ← edited

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


  • -2
    nductp  commented on Aug. 8, 2024, 1:53 a.m.

    dạ anh chị cho e hỏi vì sao bài e dùng segmentree kiểu này lại bị WA ạ,e cảm ơn nhiều https://ideone.com/DONBnI


  • -8
    baodai  commented on July 17, 2024, 12:59 a.m.

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


  • -3
    huyhoctin2023  commented on April 30, 2024, 9:46 a.m.

    hello


  • 12
    Ceaturs  commented on April 2, 2024, 9:36 a.m. ← edited

    Bài này có nghĩa là đếm có bao nhiêu số lớn hơn số trước nó. ở testcase mẫu là 3 1 2.

    với i=1 là 3 thì ko có số nào lớn hơn nên là 0.

    với i=2 là 1 thì có 3 (3>1) lớn hơn nên là 1 số.

    với i=3 là 2 thì có số 3 (3>2) lớn hơn nên là 1 số nữa.

    => có 2 số


  • -6
    nhan19042007  commented on Oct. 12, 2023, 6:53 a.m. ← edit 3

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


  • 5
    nogo007akapkn  commented on Sept. 29, 2023, 4:07 p.m. ← edit 13

    My Sol:

    Khởi tạo cây IT với nút id quản lý đoạn (l,r) là số lượng số trong đoạn (l,r) đã được nhập vào. Với mỗi giá trị x vừa nhập vào chúng ta cộng kết quả với số lượng các số lớn hơn tức là các số trong đoạn(x+1,1e6). Sau đó cập nhật giá trị x vào trong cây (cộng 1 vào tất cả các nút quản lý đoạn có chứa x). Có thể dùng cây BIT để tối ưu hóa thời gian nhưng ở đây mình thấy dùng cây IT là đủ rồi

    Code (cũ nên hơi xấu) :

    https://ideone.com/omUWVj


    • -15
      TLinhA5K64CBH  commented on Sept. 30, 2023, 12:21 a.m.

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


  • -30
    hoaibang2888  commented on June 26, 2023, 8:38 a.m. ← edited

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


  • -144
    Myee  commented on Feb. 7, 2023, 4:18 p.m.

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


  • 81
    giorzang  commented on Nov. 30, 2021, 2:14 p.m. ← edit 2

    Minh lo comment nham loi giai ma k biet delete o dau :v xin phep edit binh luan a