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:
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
bai nay fenwick cung dc nhe
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.
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
thật ra bài này với giới hạn n = 60000 thì với việc for trâu 2 vòng thì độ phức tạp chỉ lên tới 36*1e8, nếu bạn may mắn thì với một cái code trâu vẫn AC được cho dùng là không thực sự giải quyết được bài này!
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
pro qua a
seg+lazy
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
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
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
hello
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ố
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
My Sol:
Code (cũ nên hơi xấu) :
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
13
14
15
16
17
18
19
20
21
22
23
23
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
27
28
28
29
30
31
32
33
34
35
36
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
nah i'd lose
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
29
30
31
32
33
34
35
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Minh lo comment nham loi giai ma k biet delete o dau :v xin phep edit binh luan a