Đếm Đoạn Bao Chứa
Đề bài
Cho $n$ đoạn, nhiệm vụ của bạn là đếm xem với mỗi đoạn chứa bao nhiêu đoạn khác và có bao nhiêu đoạn khác chứa nó.
Đoạn $[a, b]$ chứa đoạn $[c, d]$ nếu $a \le c$ và $d \le b$.
Input:
- Dòng đầu vào đầu tiên có một số nguyên $n$ $(1 \le n \le 2 \times 10^5)$ - số lượng đoạn.
- Sau này, có $n$ dòng mô tả các đoạn. Mỗi dòng có hai số nguyên $x$ và $y$ $(1 \le x < y \le 10^9)$ - đoạn là $[x, y]$.
- Bạn có thể giả định rằng không có đoạn nào xuất hiện nhiều hơn một lần trong đầu vào.
Output:
- Trước tiên, in một dòng mô tả cho mỗi đoạn (theo thứ tự đầu vào) có bao nhiêu đoạn khác mà nó chứa.
- Sau đó, in một dòng mô tả cho mỗi đoạn (theo thứ tự đầu vào) có bao nhiêu đoạn khác chứa nó.
Subtask:
- 50% số test đầu tiên có $n \le 10^4$.
- 50% số test còn lại không có giới hạn gì thêm.
4
1 6
2 4
4 8
3 62 0 0 0
0 1 0 1Lời mở đầu
Bài này mình được một bạn học viên hỏi nên sẵn tiện mình viết bài giải chi tiết để nhiều bạn được tham khảo luôn. Hy vọng mang đến được giá trị cho các bạn 😇.
Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.
Nộp bài trên CLUE OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
Hiểu đềĐoạn nào chứa đoạn nào?
Mình sẽ giải thích lại đề bài như sau cho bạn nào chưa hiểu: ta được cho danh sách $N$ đoạn thẳng, mỗi đoạn thẳng có 2 thông số là $a$, $b$ tức là xuất phát từ $a$ và kết thúc ở $b$. Với mỗi đoạn thẳng trong danh sách ta hãy đếm xem:
- nó bao chứa được bao nhiêu đoạn thẳng còn lại?
- có bao nhiêu đoạn thẳng còn lại bao chứa nó?
Kết quả xuất ra gồm 2 dòng. Dòng đầu tiên có $N$ số nguyên, số thứ $i$ cho biết đoạn thẳng thứ $i$ trong input chứa được bao nhiêu đoạn thẳng còn lại. Dòng thứ 2 cũng là $N$ số nguyên, số thứ $i$ cho biết có bao nhiêu đoạn thẳng còn lại bao chứa đoạn thẳng thứ $i$.
Ví dụ đề trên trục số: đoạn cam $[1, 6]$ bao trọn 2 đoạn xanh $[2, 4]$ và $[3, 6]$; đoạn xám $[4, 8]$ thò ra ngoài nên không ai chứa nó và nó cũng không chứa ai.
Như ví dụ đề bài đưa ra, ta hiểu là đoạn $\{1, 6\}$ bao chứa 2 đoạn khác (là $\{2, 4\}$ và $\{3, 6\}$) và không có đoạn nào bao chứa được nó. Đoạn $\{2, 4\}$ không bao chứa được đoạn nào và có 1 đoạn bao chứa được nó (là $\{1, 6\}$). Đoạn $\{4, 8\}$ không bao chứa được đoạn nào và cũng không có đoạn nào bao chứa được nó. Đoạn $\{3, 6\}$ không bao chứa được đoạn nào và có 1 đoạn bao chứa được nó (là $\{1, 6\}$). Đó là lý do kết quả xuất ra 2 dòng là 2 0 0 0 và 0 1 0 1.
Nhìn giới hạn để định hình độ phức tạp
Một yếu tố quan trọng không được bỏ qua trong các bài giải thuật đó là phạm vi giới hạn độ lớn của dữ liệu. Bài này $N$ tối thiểu là 1, tối đa là $2 \cdot 10^5$; điểm đầu, cuối mỗi đoạn tối thiểu là 1, tối đa là $10^9$. Thực ra cái ta cần quan tâm nhất chính là $N$ vì nó là số lượng các đoạn thẳng.
Khi $N$ tối đa $2 \cdot 10^5$ thì muốn chạy trong 1 giây, toàn bộ bài làm phải có độ phức tạp $O(N \log N)$ trở xuống. Nếu $O(N^2)$ ($N$ lũy thừa 2, phép ^ ở đây là ký hiệu lũy thừa chứ không phải phép xor bit nha các bạn) thì chắc chắn bị TLE: $N^2 = 4 \cdot 10^{10}$ quá giới hạn $10^8$ rồi. Còn $N \log N \approx 18 \cdot 2 \cdot 10^5 = 3{,}6 \cdot 10^6$ thì ít hơn ngưỡng $10^8$ nên yên tâm không bị TLE. Nên nhìn vào 1 bài ta nhìn ngay giới hạn mà ước tính thuật toán phải có độ phức tạp bao nhiêu, từ đó định hình ra cách giải quyết.
Cách 1 · 50%Vét cạn O(N²)
Khi đã hiểu rõ đề rồi thì giờ chúng ta bắt tay vào giải quyết nhé. Trước tiên ta chỉ tập trung vào yêu cầu đầu tiên: với mỗi đoạn thẳng, kiểm tra xem nó bao chứa bao nhiêu đoạn còn lại?
Thì quá dễ để làm điều này: với mỗi đoạn a[i] ta xét nó với toàn bộ các đoạn a[j] còn lại trong danh sách. a[i] bao chứa a[j] khi a[i].first <= a[j].first và đồng thời a[i].second >= a[j].second. Cứ với từng a[i] ta đếm qua tất cả a[j] rồi in ra kết quả, đơn giản vậy thôi.
Còn với yêu cầu ngược lại (có bao nhiêu đoạn a[j] bao chứa a[i]) thì ta copy lại toàn bộ code của yêu cầu trước, chỗ nào gọi a[i] thì sửa thành a[j], chỗ nào gọi a[j] thì sửa thành a[i]. Tức là điều kiện lúc này thành: a[j].first <= a[i].first và đồng thời a[j].second >= a[i].second.
Source code để các bạn tham khảo (C++ nộp được 2.5/5 điểm, Python nộp được 1/5 điểm):
Cách 1: vét cạn O(N²) – qua 50% số test
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
vector<pair<int, int>> a(n);
for(int i = 0; i < n; ++i){
cin >> a[i].first >> a[i].second;
}
for(int i = 0; i < n; ++i){
int cnt = -1;
for(int j = 0; j < n; ++j){
if(a[i].first <= a[j].first && a[i].second >= a[j].second){
cnt++;
}
}
cout << cnt << " ";
}
cout << endl;
for(int i = 0; i < n; ++i){
int cnt = -1;
for(int j = 0; j < n; ++j){
if(a[j].first <= a[i].first && a[j].second >= a[i].second){
cnt++;
}
}
cout << cnt << " ";
}
return 0;
}import sys
data = sys.stdin.read().strip().split()
n = int(data[0])
a = []
idx = 1
for _ in range(n):
x = int(data[idx])
y = int(data[idx + 1])
idx += 2
a.append((x, y))
res1 = []
for i in range(n):
cnt = -1
for j in range(n):
if a[i][0] <= a[j][0] and a[i][1] >= a[j][1]:
cnt += 1
res1.append(str(cnt))
print(" ".join(res1))
res2 = []
for i in range(n):
cnt = -1
for j in range(n):
if a[j][0] <= a[i][0] and a[j][1] >= a[i][1]:
cnt += 1
res2.append(str(cnt))
print(" ".join(res2))Giải thích một số chỗ trong code
ios::sync_with_stdio(0); cin.tie(0);2 dòng đầu tiên của hàm main sẽ giúp đẩy nhanh tốc độ nhập xuất dữ liệu nếu các bạn đang code theo ngôn ngữ C++ (để hiểu vì sao thì các bạn cứ gõ mấy từ này lên Google là sẽ ra rất nhiều bài viết giải thích nhé), nên kinh nghiệm trong các bài cần nhập xuất nhiều, như bài này input có thể lên đến $4 \cdot 10^5$ số cần nhập và cũng $4 \cdot 10^5$ số cần xuất, ta nên để thêm 2 dòng này vào đầu để chương trình chạy nhanh hơn. Tất nhiên nếu các bạn code theo cú pháp của C thì chẳng cần mấy dòng đó làm gì, tuy nhiên thường khi code các bài lập trình thi đấu thế này ta dùng C++ vì cú pháp ngắn gọn cũng như nhiều hỗ trợ của nó, vậy nên bạn nào code C++ thì nhớ thêm 2 dòng này vào đầu hàm main nhé.- Sử dụng biến cấu trúc có 2 thành phần tương ứng điểm đầu và điểm cuối của đoạn thẳng thì ta dùng ngay cấu trúc
pairđã được hỗ trợ sẵn với 2 thành phầnfirstvàsecond. Nếu không dùngpairthì phải tự xây dựngstruct Datavới 2 thành phần tương tự thì lại dài dòng thêm. Và mảng thì ta dùng luônvectorcho tiện nhé các bạn. - Khi xét
a[i]vàa[j]cần đảm bảo tụi nó không trùng nhau, tức là $i \ne j$, vì sẽ không có chuyệna[i]bao chứa chínha[i]. Nhưng thêmif(i != j)thì số lần kiểm tra điều kiện nhiều và dài dòng code thêm. Trong khi đó nếu $i = j$ thì chắc chắn tụi nó bao chứa nhau (điều kiện là<=và>=có trường hợp bằng). Vậy để đơn giản ta cứ để tụi nó tự do xét rồi sau cùng đáp án trừ đi 1, hoặc như code trên mình khởi tạocnt = -1thì coi như đã trừ đi 1 sẵn rồi. Còn bạn nào khởi tạocnt = 0thì khi in ra phải nhớ incnt - 1nhé.
Thời gian: $O(N)$ đọc dữ liệu + $O(N^2)$ cho yêu cầu thứ nhất + $O(N^2)$ cho yêu cầu thứ hai. Theo quy tắc cộng BigO ta lấy thành phần lớn nhất nên độ phức tạp là $O(N^2)$. Với $N = 2 \cdot 10^5$ thì $N^2 = 4 \cdot 10^{10}$ vượt quá ngưỡng $10^8$ trong 1 giây nên chắc chắn bị TLE. Tuy nhiên ta code ra nó để tận dụng làm công cụ kiểm tra tính chính xác cho cách làm tối ưu hơn nhé.
Cách 2 · TLESắp xếp theo đầu đoạn + mảng
Giờ ta sẽ bàn về một cách làm tốt hơn. Trước tiên làm yêu cầu đầu tiên: xét xem mỗi a[i] bao chứa bao nhiêu đoạn a[j] khác.
Mấu chốt để a[i] bao chứa a[j] là 2 điều kiện kết hợp: a[i].first <= a[j].first && a[i].second >= a[j].second. Vậy ta xét tất cả các đoạn a[j] có first >= a[i].first, rồi trong số những đoạn đó đếm xem có bao nhiêu đoạn mà second <= a[i].second, đây chính là đáp án.
Bước 1: sắp xếp tăng dần theo first
Ta sắp xếp danh sách tăng dần theo first. Khi đó với mỗi vị trí a[i], toàn bộ các phần tử từ a[i] đến cuối đều có first >= a[i].first.
Tuy nhiên các bạn lưu ý: các đoạn có thể trùng điểm đầu, nên nói "những đoạn có first >= a[i].first là từ index $i$ đến cuối" là không đúng, có khi nó bắt đầu từ index trước đó. Ví dụ các đoạn đã tăng dần theo first là:
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 5}, {4, 6}
Khi $i = 2$ (đoạn $\{1, 4\}$) thì rõ ràng đoạn đầu tiên có first >= 1 là $i = 0$ đúng không các bạn. Nên ta dùng hàm lower_bound để tìm ra index đầu tiên có first >= a[i].first, gọi là start. Từ start đến cuối mảng là những đoạn thỏa mãn tiêu chí đầu tiên.
Bước 2: duyệt i từ cuối về đầu
Đến đây chắc các bạn cũng nhận ra là nên duyệt $i$ từ $n - 1$ về $0$ đúng không? Vì nếu duyệt từ đầu thì danh sách từ start đến cuối của lần sau lại bị trùng với lần trước. Còn duyệt từ cuối về thì sau mỗi lần, danh sách các đoạn cần thêm vào để thống kê chỉ là từ start mới đến $i$ hiện tại thôi (từ sau $i$ đến cuối đã được đưa vào ở các lần trước rồi). Chỗ này hơi lằng nhằng nhưng hi vọng các bạn hiểu hihi.
start, ta đưa các giá trị second của các đoạn từ start đến $i$ vào một tập hợp $X$. Khi cần, ta thống kê ngay trong $X$ có bao nhiêu phần tử $\le$ a[i].second, trừ đi 1 (chính nó) là ra đáp án.Yêu cầu thứ 2 (có bao nhiêu đoạn bao chứa a[i]) làm tương tự ngược lại: duyệt từ đầu, đưa vào $X$ các đoạn có first <= a[i].first (dùng upper_bound tìm finish), rồi đếm trong $X$ có bao nhiêu phần tử $\ge$ a[i].second.
Em nhập các đoạn (mỗi đoạn 2 số $x\ y$, ngăn cách bởi dấu ;) rồi bấm Tiếp để xem từng bước quét và đếm:
Tập hợp X dùng mảng thì sao?
Nếu tập hợp $X$ là mảng: sắp xếp mảng tăng dần rồi dùng upper_bound tìm vị trí đầu tiên có giá trị > a[i].second, gọi là finish. Khi đó finish - 1 là vị trí cuối cùng thỏa mãn, nên số lượng chính là finish (ví dụ finish = 5 thì index 0 đến 4 là 5 phần tử). Tìm kiếm thì rất nhanh, chỉ $O(\log N)$.
Nhưng vấn đề là mảng liên tục cần thêm giá trị vào và phải giữ trật tự tăng dần:
- Cứ thêm vào rồi gọi
sort: mỗi lần $O(N \log N)$, bị gọi đi gọi lại $N$ lần thì thành $O(N \cdot N \log N)$, thậm chí còn tệ hơn cả vét cạn, rắc rối dài dòng mà còn tệ hơn. - Dùng kiểu sắp xếp chèn (Insertion Sort): tìm vị trí chèn nhanh nhờ tìm kiếm nhị phân, nhưng bước chèn thì các phần tử phía sau phải nhích xuống 1 ô, trường hợp xấu nhất $O(N)$ mỗi lần, $N$ lần thành $O(N^2)$, lại ngang vét cạn.
Mình có thử code nhanh theo hướng thêm phần tử vào cuối mảng rồi gọi sort lại, sau đó dùng upper_bound. Đúng như dự đoán nộp bị TLE nha các bạn :)) (C++ được 1/5 điểm, Python được 2.5/5 điểm). Nhưng mình cũng ráng code để các bạn tham khảo cách làm luôn, trong code mình xử lý luôn cả yêu cầu thứ 2:
Cách 2: sort + mảng (sort lại liên tục) – TLE
#include <bits/stdc++.h>
using namespace std;
struct Data{
int x, y, id;
};
Data a[200000];
bool cmp(const Data &a, const Data &b){
return a.x < b.x;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i].x >> a[i].y;
a[i].id = i;
}
sort(a, a + n, cmp);
int b[n];
vector<int> c;
for(int i = n - 1; i >= 0; --i){
int start = lower_bound(a, a + n, Data{a[i].x}, cmp) - a;
for(int j = i; j >= start; --j){
c.push_back(a[j].y);
}
sort(c.begin(), c.end());
for(int j = i; j >= start; --j){
b[a[j].id] = upper_bound(c.begin(), c.end(), a[j].y) - c.begin() - 1;
}
i = start;
}
for(int i = 0; i < n; ++i){
cout << b[i] << " ";
}
cout << endl;
c.clear();
for(int i = 0; i < n; ++i){
int finish = upper_bound(a, a + n, Data{a[i].x}, cmp) - a;
for(int j = i; j < finish; ++j){
c.push_back(a[j].y);
}
sort(c.begin(), c.end());
for(int j = i; j < finish; ++j){
b[a[j].id] = (int)c.size() - (lower_bound(c.begin(), c.end(), a[j].y) - c.begin()) - 1;
}
i = finish - 1;
}
for(int i = 0; i < n; ++i){
cout << b[i] << " ";
}
return 0;
}import sys
from bisect import bisect_left, bisect_right
data = list(map(int, sys.stdin.read().split()))
n = data[0]
idx = 1
a = []
for i in range(n):
x = data[idx]
y = data[idx + 1]
idx += 2
a.append([x, y, i])
a.sort(key=lambda t: t[0])
b = [0] * n
c = []
i = n - 1
while i >= 0:
x_i = a[i][0]
start = bisect_left(a, x_i, key=lambda t: t[0])
for j in range(i, start - 1, -1):
c.append(a[j][1])
c.sort()
for j in range(i, start - 1, -1):
b[a[j][2]] = bisect_right(c, a[j][1]) - 1
i = start - 1
print(" ".join(map(str, b)))
c.clear()
i = 0
while i < n:
x_i = a[i][0]
finish = bisect_right(a, x_i, key=lambda t: t[0])
for j in range(i, finish):
c.append(a[j][1])
c.sort()
for j in range(i, finish):
b[a[j][2]] = len(c) - bisect_left(c, a[j][1]) - 1
i = finish
print(" ".join(map(str, b)))Giải thích một số chỗ trong code
- Mảng
Data a[200000]khai báo bên ngoài hàmmainlàm biến toàn cục. Mình không dám khai báoData a[n]trongmainvì $n$ tối đa $2 \cdot 10^5$, mỗi phần tử có nhiều thành phần nên tổng số giá trị cần chứa rất lớn. Theo kinh nghiệm của mình nếu vượt quá $3 \cdot 10^5$ phần tử thì tốt nhất không dùng mảng tĩnh trong hàm vì bộ nhớ stack có thể không chứa nổi; đem ra ngoài làm biến toàn cục thì nó không dùng vùng nhớ stack nên chứa được lớn hơn. Hoặc dùng cấp phát độngData *a = new Data[n];, hoặc dùngvector. - Biến
xchính làfirst,ylàsecond, đặt cho ngắn gọn. Mình tạostruct Datathay vìpairvì cần thêm trườngid: sau khi sắp xếp thì thứ tự các đoạn đã bị thay đổi so với ban đầu, nênidlưu lại vị trí ban đầu. Kết quả của đoạna[i]được lưu vàob[a[i].id], sau cùng in mảngbtừ 0 đến $N - 1$ là đúng thứ tự input. - Mỗi kết quả
b[a[i].id]phải nhớ trừ 1 vì không tính trường hợp chính nó bao chứa chính nó. - Tìm ra
startxong, ta duyệt ngược từ $i$ vềstartđưa các giá trịa[j].yvào mảngc, rồi gọisort, rồi tìmupper_boundvới từnga[j].y. Sau cùng gáni = startđể lần lặp tiếp theo--isẽ xét tiếp từ ngay trướcstart, vì từstartđến cuối đã xét rồi. Trước khi sang yêu cầu thứ 2 phải nhớc.clear()để chuẩn bị chứa danh sách mới.
Cách 3 · 100%Ordered set "độ lại" O(N log N)
Cách làm ở trên về mặt tư tưởng thì đó là tư tưởng tối ưu nha các bạn, nhưng vì cấu trúc mảng có hạn chế như vậy nên ta phải xem xét những cấu trúc dữ liệu khác phù hợp hơn.
multiset: thêm vào thì nhanh, nhưng đếm thì chậm
Cấu trúc multiset chứa được nhiều phần tử trùng nhau, các phần tử thêm vào tự được sắp tăng dần, mỗi lần thêm tốn $O(\log N)$, thêm $N$ phần tử là $O(N \log N)$, rất ổn. Được như vậy vì bản chất multiset là cây nhị phân tìm kiếm, và nó cũng hỗ trợ lower_bound, upper_bound.
Tuy nhiên lower_bound/upper_bound của nó chỉ trả về con trỏ trỏ vào phần tử tìm thấy, trong khi ta cần biết từ đầu đến vị trí đó có bao nhiêu phần tử. Với mảng thì dễ vì các ô nhớ liền kề nhau, còn với cây thì các vùng nhớ rời rạc do cấp phát động. Muốn biết số lượng ta phải duyệt từ phần tử đầu đến phần tử tìm thấy (gọi hàm distance cũng làm tương tự), tức là tìm kiếm tuần tự; nếu điều đó cứ liên tục xảy ra thì sau cùng lại là $O(N^2)$.
ordered_set: thêm O(log N), đếm cũng O(log N)
Lúc này có 1 cấu trúc dữ liệu không thể nào phù hợp hơn, đó là ordered_set trong C++ (thư viện policy based data structures của GNU). Cũng như multiset, thêm 1 phần tử vào và tự động sắp thứ tự chỉ với $O(\log N)$. Và nó có hỗ trợ hàm:
Đây chính là cái ta đang cần! Muốn đếm số phần tử $\le$ a[i].y thì truyền $k$ = a[i].y + 1, vì $<$ a[i].y + 1 $\Leftrightarrow$ $\le$ a[i].y. Vậy đưa phần tử vào là $O(N \log N)$, tra cứu đáp án của $N$ đoạn cũng $O(N \log N)$, tổng quát $O(N \log N)$, đẹp để không bị TLE.
Bạn nào muốn hiểu sâu hơn về ordered_set thì xem bài viết này trên GeeksforGeeks nhé: Ordered Set and GNU C++ PBDS.
Nhưng mà… ordered_set không chứa phần tử trùng 😭
Nếu bạn đang hào hứng và nghĩ rằng bài này vậy là xong thì xin chia buồn với các bạn: ordered_set cũng tương tự như set, nó không hỗ trợ phần tử trùng. Trong khi bài hiện tại các giá trị a[i].y đưa vào có thể bị trùng nhau (nhiều đoạn chung điểm cuối). Vậy nên téo teo tèo teo cấu trúc dữ liệu này không áp dụng được rồi ahuhu 😭 Có set thì có multiset, vậy liệu có "multi ordered_set" chăng? Rất tiếc là không 😭
Tuy nhiên hãy vui lên nào, chúng ta có một phiên bản mà mình gọi vui là được "độ lại" của ordered_set: lưu cặp {giá trị, chỉ số tăng dần idx}. Hai cặp có cùng giá trị nhưng khác idx thì vẫn là 2 phần tử khác nhau, nên giờ nó chứa được giá trị trùng, mọi thứ vẫn y như cũ, chỉ có cú pháp dài thêm 1 chút. Các bạn xem chi tiết tại bài viết: How to store duplicate elements in ordered set.
Tập chứa các giá trị $4, 6, 6, 8$ dưới dạng cặp. order_of_key({6 + 1, -1}) = order_of_key({7, -1}) = 3: có 3 cặp nhỏ hơn $(7, -1)$, đúng bằng số giá trị $\le 6$ (cả 2 số 6 trùng nhau đều được đếm).
Vậy giờ chúng ta ứng dụng cấu trúc dữ liệu được độ lại này vào bài nhé, code C++ này đã full 5/5 điểm nha các bạn. Mọi tư tưởng xử lý đều y như cách làm với mảng ở trên, chỉ khác là dùng ordered_set được độ lại thôi:
#include <bits/stdc++.h>
using namespace std;
// Header files to implement ordered set
// Common file
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// namespace necessary for GNU based
// policy based data structures
using namespace __gnu_pbds;
// Declaring ordered_set for pair<int,int>
typedef tree<pair<int,int>, null_type,
less<pair<int,int>>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set_pair;
struct Data{
int x, y, id;
};
Data a[200000];
bool cmp(const Data &a, const Data &b){
return a.x < b.x;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for(int i = 0; i < n; ++i){
cin >> a[i].x >> a[i].y;
a[i].id = i;
}
sort(a, a + n, cmp);
int idx = 0;
ordered_set_pair mySet;
int b[n];
for(int i = n - 1; i >= 0; --i){
int start = lower_bound(a, a + n, Data{a[i].x}, cmp) - a;
for(int j = i; j >= start; --j){
mySet.insert({a[j].y, idx++});
}
for(int j = i; j >= start; --j){
b[a[j].id] = mySet.order_of_key({a[j].y + 1, -1}) - 1;
}
i = start;
}
for(int i = 0; i < n; ++i){
cout << b[i] << " ";
}
cout << endl;
mySet.clear();
idx = 0;
for(int i = 0; i < n; ++i){
int finish = upper_bound(a, a + n, Data{a[i].x}, cmp) - a;
for(int j = i; j < finish; ++j){
mySet.insert({a[j].y, idx++});
}
for(int j = i; j < finish; ++j){
b[a[j].id] = (int)mySet.size() - mySet.order_of_key({a[j].y, -1}) - 1;
}
i = finish - 1;
}
for(int i = 0; i < n; ++i){
cout << b[i] << " ";
}
return 0;
}import sys
from bisect import bisect_left, bisect_right
# Python không có sẵn ordered_set, nên mình dùng cây Fenwick (BIT)
# trên các giá trị y đã nén: đếm số phần tử <= v trong O(log N)
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
xs = data[1:2 * n + 1:2]
ys = data[2:2 * n + 2:2]
vals = sorted(set(ys))
m = len(vals)
pos = [bisect_left(vals, y) + 1 for y in ys] # y nén về 1..m
order = sorted(range(n), key=lambda k: xs[k])
bit = [0] * (m + 1)
def add(p):
while p <= m:
bit[p] += 1
p += p & -p
def query(p): # số phần tử có vị trí nén <= p
s = 0
while p > 0:
s += bit[p]
p -= p & -p
return s
b = [0] * n
# Yêu cầu 1: duyệt từ cuối, mỗi nhóm cùng x thêm hết rồi mới hỏi
i = n - 1
while i >= 0:
start = i
while start > 0 and xs[order[start - 1]] == xs[order[i]]:
start -= 1
for j in range(i, start - 1, -1):
add(pos[order[j]])
for j in range(i, start - 1, -1):
k = order[j]
b[k] = query(pos[k]) - 1
i = start - 1
print(" ".join(map(str, b)))
# Yêu cầu 2: duyệt từ đầu, đếm số y >= y hiện tại
bit = [0] * (m + 1)
total = 0
i = 0
while i < n:
finish = i
while finish < n and xs[order[finish]] == xs[order[i]]:
finish += 1
for j in range(i, finish):
add(pos[order[j]])
total += finish - i
for j in range(i, finish):
k = order[j]
b[k] = total - query(pos[k] - 1) - 1
i = finish
print(" ".join(map(str, b)))Giải thích một số chỗ trong code
- Kiểu
ordered_set_pairlà cây đỏ đen (rb_tree_tag) chứapair<int,int>có thêm thông tin thứ tự (tree_order_statistics_node_update) nên mới có hàmorder_of_key. - Yêu cầu 1:
order_of_key({a[j].y + 1, -1})đếm số cặp nhỏ hơn{y + 1, -1}, tức là mọi cặp có giá trị $\le y$ (bất kểidx), trừ 1 là bỏ chính nó. - Yêu cầu 2:
order_of_key({a[j].y, -1})đếm số cặp có giá trị $< y$, lấymySet.size()trừ đi là ra số cặp có giá trị $\ge y$, trừ 1 là bỏ chính nó. - Python không có sẵn
ordered_set, nên bản Python mình viết thêm dùng cây Fenwick (BIT) trên các giá trị $y$ đã nén, cũng thêm/đếm trong $O(\log N)$.
Nhận xét
Đăng nhận xét