Dãy nghịch thế

Xem dạng PDF
Gửi bài giải
Điểm: 0,08 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 512M
Input: stdin
Output: stdout
Nguồn bài:
IOICamp Marathon 2005-2006
Dạng bài
Ngôn ngữ cho phép
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

Bình luận

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


  • 1
    Free_De_La_Zenith  đã bình luận lúc 1, Tháng 3, 2025, 15:41

    seg+lazy


  • -5
    minhtuanvp2011  đã bình luận lúc 22, Tháng 10, 2024, 12:32

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -8
    phamducminh538  đã bình luận lúc 12, Tháng 8, 2024, 6:54 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -3
    nductp  đã bình luận lúc 8, Tháng 8, 2024, 1:53

    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


  • -7
    baodai  đã bình luận lúc 17, Tháng 7, 2024, 0:59

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -3
    huyhoctin2023  đã bình luận lúc 30, Tháng 4, 2024, 9:46

    hello


  • 10
    Ceaturs  đã bình luận lúc 2, Tháng 4, 2024, 9:36 ← chỉnh sửa

    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ố


  • -5
    nhan19042007  đã bình luận lúc 12, Tháng 10, 2023, 6:53 ← sửa 3

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 3
    nogo007akapkn  đã bình luận lúc 29, Tháng 9, 2023, 16:07 ← sửa 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  đã bình luận lúc 30, Tháng 9, 2023, 0:21

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -29
    hoaibang2888  đã bình luận lúc 26, Tháng 6, 2023, 8:38 ← chỉnh sửa

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


    • -19
      UruLuka  đã bình luận lúc 20, Tháng 8, 2023, 13:46

      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


      • -10
        thanhthanhh5  đã bình luận lúc 14, Tháng 12, 2023, 0:46

        Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


        • -10
          ElmiraAthena  đã bình luận lúc 19, Tháng 2, 2024, 3:04

          Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


          • -10
            anhquanbaoloc  đã bình luận lúc 19, Tháng 2, 2024, 3:05

            Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


            • -10
              vdtue  đã bình luận lúc 12, Tháng 3, 2024, 0:48

              Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


              • -10
                teudepdzai  đã bình luận lúc 31, Tháng 3, 2024, 12:25

                Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


                • -5
                  ngunhatdtt  đã bình luận lúc 1, Tháng 4, 2024, 3:10

                  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


                  • -5
                    WamiITB  đã bình luận lúc 1, Tháng 4, 2024, 3:11

                    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


                    • -11
                      amogus123  đã bình luận lúc 1, Tháng 4, 2024, 3:11

                      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


                      • -5
                        WhiteZeros1410  đã bình luận lúc 1, Tháng 4, 2024, 3:12

                        Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


                        • -10
                          duybinh_cbl  đã bình luận lúc 1, Tháng 4, 2024, 3:12

                          Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


                          • -4
                            testcuzImsodumb  đã bình luận lúc 1, Tháng 4, 2024, 3:13

                            13


                            • -5
                              huyleee  đã bình luận lúc 1, Tháng 4, 2024, 3:14

                              Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


                              • -4
                                hhmq_t11_  đã bình luận lúc 1, Tháng 4, 2024, 3:14

                                15


                                • -4
                                  asus_user  đã bình luận lúc 1, Tháng 4, 2024, 3:16

                                  16


                                  • -5
                                    ngunhatdttt  đã bình luận lúc 1, Tháng 4, 2024, 3:16

                                    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


                                    • -5
                                      SussyDaddy  đã bình luận lúc 1, Tháng 4, 2024, 3:17

                                      Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


                                      • -5
                                        in_site  đã bình luận lúc 1, Tháng 4, 2024, 3:20

                                        Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


                                        • -5
                                          Retardlord  đã bình luận lúc 1, Tháng 4, 2024, 3:20

                                          Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


                                          • -1
                                            khoihk20  đã bình luận lúc 1, Tháng 4, 2024, 8:27

                                            21


                                            • 0
                                              VVUU  đã bình luận lúc 1, Tháng 4, 2024, 8:27

                                              22


                                              • -3
                                                DuongNhanAC  đã bình luận lúc 1, Tháng 4, 2024, 8:56

                                                23

                                                23

                                                23

                                                #include <bits/stdc++.h>
using namespace std;

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    cout << "23\n";
    return 0;
}

                                                print(23)

                                                • -6
                                                  nductp  đã bình luận lúc 18, Tháng 6, 2024, 15:38

                                                  Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


                                          • -20
                                            hieuhfgr  đã bình luận lúc 1, Tháng 4, 2024, 7:06

                                            Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -134
    Myee  đã bình luận lúc 7, Tháng 2, 2023, 16:18

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • 80
    giorzang  đã bình luận lúc 30, Tháng 11, 2021, 14:14 ← sửa 2

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