Điểm chung
Đề bài
Trên trục số Ox, cho $N$ đoạn thẳng, mỗi đoạn thẳng được xác định bởi hai điểm đầu và cuối là hai số nguyên. Một điểm $M$ được gọi là nằm trong đoạn thẳng $AB$ nếu $A \le M \le B$.
Yêu cầu: đếm xem có bao nhiêu điểm có toạ độ nguyên nằm trong đúng $K$ đoạn thẳng.
Dữ liệu vào
- Dòng đầu tiên gồm hai số nguyên $N$ và $K$ ($1 \le K \le N \le 10^5$);
- $N$ dòng sau, mỗi dòng gồm hai số nguyên $a, b$ mô tả hai điểm đầu và cuối của đoạn thẳng ($1 \le a \le b \le 10^{18}$).
Kết quả
- Một số nguyên duy nhất là số lượng điểm có toạ độ nguyên nằm trong đúng $K$ đoạn thẳng.
Ràng buộc:
- Có 50% số test ứng với 50% số điểm của bài thoả mãn: $a, b \le 10^3$;
- 30% số test khác ứng với 30% số điểm của bài thoả mãn: $K = N$;
- 20% số test còn lại ứng với 20% số điểm của bài không có ràng buộc gì thêm.
3 2
1 5
2 8
3 73Điểm có toạ độ 2 nằm trong 2 đoạn thẳng: đầu tiên và thứ hai.
Điểm có toạ độ 6, 7 nằm trong 2 đoạn thẳng: thứ hai và thứ ba.
3 1
1 5
2 8
3 72Điểm có toạ độ 1 chỉ nằm trong đoạn thẳng đầu tiên.
Điểm có toạ độ 8 chỉ nằm trong đoạn thẳng thứ ba.
3 3
1 5
2 8
3 73Lờ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:
50%Cách 1: thống kê số lần xuất hiện bằng map
Một cách làm rất đơn giản cho bài này mà chắc nhiều bạn sẽ nhìn ra: mỗi đoạn thẳng gồm 2 điểm $a$, $b$ với $a$ là điểm đầu, $b$ là điểm cuối. Với mỗi đoạn thẳng ta cứ lặp xét tất cả các điểm từ $a$ đến $b$ và đánh dấu số lần xuất hiện của các điểm đó được +1. Cứ thế xét qua tất cả các đoạn thẳng là ta có thống kê cụ thể từng điểm phân biệt xuất hiện bao nhiêu lần. Sau đó đếm số lượng các điểm xuất hiện đúng $K$ lần thì đó là đáp án.
Ví dụ với các test mẫu đề cho đều có 3 đoạn thẳng là (1, 5), (2, 8), (3, 7) thì ta thống kê như sau (ô xanh là ô vừa được +1):
| Điểm | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|
| Sau đoạn (1, 5) | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 |
| Sau đoạn (2, 8) | 1 | 2 | 2 | 2 | 2 | 1 | 1 | 1 |
| Sau đoạn (3, 7) | 1 | 2 | 3 | 3 | 3 | 2 | 2 | 1 |
Vậy khi đã thống kê ra được rồi:
- Test ví dụ 1 có $K = 2$: chỉ có 3 điểm xuất hiện 2 lần là các điểm 2, 6, 7.
- Test ví dụ 2 có $K = 1$: chỉ có 2 điểm xuất hiện 1 lần là các điểm 1, 8.
- Test ví dụ 3 có $K = 3$: chỉ có 3 điểm xuất hiện 3 lần là các điểm 3, 4, 5.
Để thống kê số lần xuất hiện của từng điểm phân biệt thì tiện nhất ta dùng cấu trúc dữ liệu map nhé các bạn, với key là điểm còn value là số lần xuất hiện.
Xem code cách 1 (map)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
map<long long, long long> mp;
while(n--){
long long a, b;
cin >> a >> b;
while(a <= b){
mp[a]++;
a++;
}
}
long long res = 0;
for(auto it = mp.begin(); it != mp.end(); ++it){
if(it->second == k){
res++;
}
}
cout << res;
return 0;
}import sys
n_k = list(map(int, sys.stdin.readline().split()))
while len(n_k) < 2:
n_k += list(map(int, sys.stdin.readline().split()))
n, k = n_k
mp = {}
count = 0
while count < n:
parts = []
while len(parts) < 2:
parts += list(map(int, sys.stdin.readline().split()))
a, b = parts
count += 1
while a <= b:
mp[a] = mp.get(a, 0) + 1
a += 1
res = 0
for key in mp:
if mp[key] == k:
res += 1
print(res)Giải thích một số chỗ trong code ở trên:
- Với mỗi đoạn thẳng ta đọc vào 2 số $a$, $b$ là điểm bắt đầu và kết thúc. Vòng lặp
while(a <= b)và cứ thếa++;để biếnalà biến duyệt từ $a$ đến $b$ luôn. Với mỗi giá trịata gọimp[a]++;: nó sẽ đi tìm xemacó trong map chưa. Nếu chưa thì thêmavào, mặc định khi khởi tạo có giá trị 0 nên++thành 1. Còn nếu đã có thì++để tăng lên 1. - Bước cuối duyệt toàn bộ map xem Node nào có số lần xuất hiện bằng đúng $K$ thì
res++;, sau cùng in rares. Việc duyệt map dùng con trỏ iterator đặt tên làit, do mình lười nên khai báo kiểuautođể compiler tự xác định kiểu, còn muốn khai báo rõ ràng thì phải làmap<long long, long long>::iterator it = mp.begin();nha các bạn. - Do $a$, $b$ có thể lên đến $10^{18}$ nên key phải dùng kiểu
long long(số nguyên 8 byte) mới chứa nổi, kiểu 4 byte nhưintsẽ không lưu nổi. Còn value là số lần xuất hiện thì tối đa cũng chỉ $N = 10^5$, nên value, $N$, $K$ dùngintlà đủ. Tuy nhiên bộ nhớ lúc nào cũng dư dả nên bình thường mình cứ đểlong longhết cho yên tâm không sợ tràn số trong bất kỳ tình huống nào.
Đánh giá độ phức tạp:
- Không gian: $O(X)$ với $X$ là số lượng điểm phân biệt trong tất cả các đoạn thẳng được đưa vào map.
- Thời gian: đọc $N$ đoạn thẳng tốn $O(N)$; mỗi đoạn lặp từ $A$ đến $B$ tốn $O(B - A + 1)$; mỗi lần tìm kiếm, cập nhật trong map tốn $O(\log X)$; sau cùng duyệt map tốn $O(X)$. Tổng cộng: $O(N \times (B - A + 1) \times \log X) + O(X)$.
$N$ tối đa chỉ $10^5$ nhưng chi phí phát sinh rất nhiều từ $A$, $B$ và $X$. Tưởng tượng gặp đoạn thẳng $A = 1$, $B = 10^{18}$ thì cách làm này toang ngay. Máy tính trung bình 1 giây chạy $10^8$ phép tính, tính sơ sơ:
Quá khủng khiếp đúng không các bạn? Chưa kể đó mới là 1 đoạn thẳng, giả sử có $N = 10^5$ đoạn đều là $A = 1$, $B = 10^{18}$ thì phải nhân thêm $10^5$ lần nữa. Đó là mới tính thời gian, chứ bộ nhớ cũng không thể lưu nổi $10^{18}$ giá trị: mỗi giá trị lưu 2 thông tin là $8 \times 2 = 16$ byte, cần $16 \times 10^{18}$ byte thì kiểu gì lưu nổi hả các bạn haha.
50%Cải tiến: unordered_map và mảng đánh dấu
Ta thấy phải nhân thêm 10 là do map được cài đặt theo cây nhị phân tìm kiếm (cụ thể là cây đỏ đen) nên mỗi thao tác tìm kiếm tốn $O(\log)$, cụ thể là $\log_2$. Khi $X = 1000$ thì $\log_2(1000) \approx 10$. Muốn tối ưu chỗ này ta dùng bảng băm (Hash Map) chỉ tốn $O(1)$ khi tìm kiếm, tức là chuyển sang unordered_map: chỉ cần đổi dòng khai báo map<long long, long long> mp; thành unordered_map<long long, long long> mp;, còn lại giữ nguyên.
unordered_map là ta đã phó mặc cho nó tự thiết kế hàm băm, nên vẫn có những trường hợp nó thiết kế "ngu" nha các bạn :))Hoặc bạn nào không biết unordered_map, hay không yên tâm giao phó cho nó thiết kế hàm băm, thì ta có thể chủ động làm luôn bằng kỹ thuật mảng đánh dấu (bản chất tư tưởng vẫn là bảng băm): tạo mảng 1001 phần tử để index từ 0 đến 1000 tương ứng tối đa 1000 điểm. Ban đầu khởi tạo tất cả là 0, mỗi điểm $a$ ta gọi vào vị trí index $a$ và tăng số lượng lên, bước này chỉ tốn $O(1)$. Sau cùng duyệt lại 1000 phần tử và kết luận. Do chính ta nắm rõ nhất quy luật của dữ liệu nên tự thiết kế "hàm băm" thì yên tâm hơn phải không nè ^^
Xem code cách 2 (mảng đánh dấu)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
long long cnt[1001] = {0};
while(n--){
long long a, b;
cin >> a >> b;
while(a <= b){
cnt[a]++;
a++;
}
}
long long res = 0;
for(long long i = 1; i <= 1000; ++i){
if(cnt[i] == k){
res++;
}
}
cout << res;
return 0;
}import sys
tokens = []
while len(tokens) < 2:
tokens += list(map(int, sys.stdin.readline().split()))
n, k = tokens[:2]
cnt = [0] * 1001
while n > 0:
line = []
while len(line) < 2:
line += list(map(int, sys.stdin.readline().split()))
a, b = line
while a <= b:
cnt[a] += 1
a += 1
n -= 1
res = 0
for i in range(1, 1001):
if cnt[i] == k:
res += 1
print(res)Đánh giá độ phức tạp: không gian $O(1000)$ của mảng cnt. Thời gian $O(1000)$ khởi tạo mảng + $O(N \times (B - A + 1))$ duyệt thống kê + $O(1000)$ duyệt mảng kết luận. Xấu nhất khi $N = 10^5$, $A = 1$, $B = 10^3$: $1000 + 10^5 \times 10^3 + 1000$ $= 2 \times 10^3 + 10^8$, theo quy tắc cộng Big O lấy thành phần lớn nhất là $10^8$, vừa đủ chạy trong 1 giây nên ăn trọn vẹn 50% test.
50%Tối ưu thêm: đếm ngay khi thống kê
Muốn chạy nhanh hơn chút thì tối ưu thêm vài chỗ. Chỗ khởi tạo mảng toàn số 0 long long cnt[1001] = {0}; có thể dùng memset cho hiệu suất nhanh hơn nhiều: long long cnt[1001]; memset(cnt, 0, sizeof(cnt));
Ngoài ra không cần bước cuối duyệt toàn bộ mảng, mà làm luôn trong bước thống kê: mỗi lần cnt[a]++; xong ta kiểm tra ngay cnt[a]:
- Nếu bằng $K$ thì
res++; - Nếu bằng $K + 1$ thì
res--;, vì trước đó nó đã bằng $K$ và ta đãres++;, giờ vượt quá $K$ thì phải trả lại.
res--;, còn về sau nó bằng $K + 2$, $K + 3$… thì không trừ gì hết, vì trước đó chỉ cộng 1 lần thì giờ chỉ trừ 1 lần. Bạn nào xét if(cnt[a] > k) { res--; } là sai đấy nhé, vì nó có thể bị trừ nhiều lần.Xem code cách 3 (đếm ngay khi thống kê)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
long long cnt[1001];
memset(cnt, 0, sizeof(cnt));
long long res = 0;
while(n--){
long long a, b;
cin >> a >> b;
while(a <= b){
cnt[a]++;
if(cnt[a] == k){
res++;
}
else if(cnt[a] == k + 1){
res--;
}
a++;
}
}
cout << res;
return 0;
}import sys
tokens = []
while len(tokens) < 2:
tokens += list(map(int, sys.stdin.readline().split()))
n, k = tokens[:2]
cnt = [0] * 1001
res = 0
while n > 0:
line = []
while len(line) < 2:
line += list(map(int, sys.stdin.readline().split()))
a, b = line
while a <= b:
cnt[a] += 1
if cnt[a] == k:
res += 1
elif cnt[a] == k + 1:
res -= 1
a += 1
n -= 1
print(res)50%Cách khác: duyệt từ Min đến Max
Ngoài các cách trên, để ăn được 50% test còn có thể làm thế này: các điểm cần xét luôn nằm trong đoạn từ $\min(A_i)$ đến $\max(B_i)$. Như ví dụ đề cho thì $\min(A_i) = 1$ và $\max(B_i) = 8$, đoạn từ 1 đến 8 bao phủ hết 3 đoạn thẳng. Ta tìm $Min$, $Max$ rồi duyệt từ $Min$ đến $Max$, với mỗi giá trị $x$ xét qua $N$ đoạn thẳng đếm xem nó nằm trong bao nhiêu đoạn (điểm $x$ nằm trong đoạn $A\,B$ khi $A \le x \le B$), đếm xong mà bằng đúng $K$ thì res++;.
Xem code cách 4 (Min đến Max)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
vector<pair<long long, long long>> a(n);
long long Max = LLONG_MIN, Min = LLONG_MAX;
for(long long i = 0; i < n; ++i){
cin >> a[i].first >> a[i].second;
Min = min(Min, a[i].first);
Max = max(Max, a[i].second);
}
long long res = 0;
for(long long x = Min; x <= Max; ++x){
long long cnt = 0;
for(long long i = 0; i < n; ++i){
if(a[i].first <= x && x <= a[i].second){
cnt++;
if(cnt > k){
break;
}
}
}
if(cnt == k){
res++;
}
}
cout << res;
return 0;
}import sys
tokens = []
while len(tokens) < 2:
tokens += list(map(int, sys.stdin.readline().split()))
n, k = tokens[:2]
a = [None] * n
Max = -9223372036854775808
Min = 9223372036854775807
read = []
while len(read) < 2 * n:
read += list(map(int, sys.stdin.readline().split()))
for i in range(n):
first = read[2 * i]
second = read[2 * i + 1]
a[i] = (first, second)
Min = min(Min, first)
Max = max(Max, second)
res = 0
x = Min
while x <= Max:
cnt = 0
for i in range(n):
if a[i][0] <= x and x <= a[i][1]:
cnt += 1
if cnt > k:
break
if cnt == k:
res += 1
x += 1
print(res)Trường hợp xấu nhất $N = 10^5$, $A = 1$, $B = 10^3$ thì lặp hết $10^5 + 10^3 \times 10^5 = 10^5 + 10^8$, tổng quát vẫn là $10^8$, chạy trong 1 giây nha các bạn. Thực tế những thông số này chỉ tương đối, vì tùy dữ liệu đầu vào, với mỗi điểm có thể kết thúc sớm khi thấy cnt đã vượt quá k thì thoát vòng lặp, không cần đếm nữa vì điểm đó chắc chắn không hợp lệ.
+30%Trường hợp K = N: giao các đoạn thẳng
Khi $K = N$ là trường hợp rất dễ làm và sẽ thật tiếc nếu bạn nào bỏ qua. Dù $A$, $B$ có thể lên đến $10^{18}$, chỉ cần $K = N$ thì mọi thứ cực kỳ đơn giản.
Tại sao? Đề yêu cầu đếm các điểm nằm trong đúng $K$ đoạn thẳng, mà $K = N$ nghĩa là đếm các điểm nằm trong đủ $N$ đoạn thẳng. Giả sử có 5 đoạn dt1, dt2, dt3, dt4, dt5: ta tìm phần giao của dt1 và dt2, không có thì kết luận 0 và dừng. Còn có thì lấy phần giao đó tìm tiếp phần giao với dt3, và cứ thế lặp lại; tại đoạn nào không còn phần giao thì kết luận 0 và dừng, còn không thì cứ tiếp tục đến hết đoạn cuối rồi in ra kết luận.
Ví dụ giữa đoạn $[1, 10]$ và $[4, 15]$ thì đoạn giao là $[4, 10]$, các bạn thử kẻ ra trên trục số sẽ thấy rõ. Còn giữa $[1, 10]$ và $[15, 30]$ thì theo công thức sẽ là $[15, 10]$, mà $15 > 10$ nên không hợp lệ, tức là không giao.
Thử với ví dụ mẫu số 3 ($N = K = 3$):
- Xét đoạn $[1, 5]$ và $[2, 8]$: đoạn giao là $[2, 5]$, hợp lệ vì $2 \le 5$ nên xét tiếp.
- Xét đoạn giao $[2, 5]$ với $[3, 7]$: đoạn giao là $[3, 5]$, hợp lệ vì $3 \le 5$. Đoạn $[3, 5]$ có $5 - 3 + 1 = 3$ điểm, đáp án in ra 3.
Mình lấy code cuối cùng của phần 1 và phát triển tiếp để lấy thêm 30% này nha các bạn:
Xem code cách 5 (thêm trường hợp K = N)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
vector<pair<long long, long long>> a(n);
long long Max = LLONG_MIN, Min = LLONG_MAX;
for(long long i = 0; i < n; ++i){
cin >> a[i].first >> a[i].second;
Min = min(Min, a[i].first);
Max = max(Max, a[i].second);
}
long long res = 0;
if(k == n){
pair<long long, long long> ans = a[0];
for(int i = 1; i < n; ++i){
ans.first = max(ans.first, a[i].first);
ans.second = min(ans.second, a[i].second);
if(ans.first > ans.second){
break;
}
}
if(ans.first <= ans.second){
res = ans.second - ans.first + 1;
}
}
else{
for(long long x = Min; x <= Max; ++x){
long long cnt = 0;
for(long long i = 0; i < n; ++i){
if(a[i].first <= x && x <= a[i].second){
cnt++;
if(cnt > k){
break;
}
}
}
if(cnt == k){
res++;
}
}
}
cout << res;
return 0;
}import sys
tokens = []
while len(tokens) < 2:
tokens += list(map(int, sys.stdin.readline().split()))
n, k = tokens[:2]
a = [None] * n
Max = -9223372036854775808
Min = 9223372036854775807
read = []
while len(read) < 2 * n:
read += list(map(int, sys.stdin.readline().split()))
for i in range(n):
first = read[2 * i]
second = read[2 * i + 1]
a[i] = (first, second)
Min = min(Min, first)
Max = max(Max, second)
res = 0
if k == n:
ans_first = a[0][0]
ans_second = a[0][1]
i = 1
while i < n:
ans_first = max(ans_first, a[i][0])
ans_second = min(ans_second, a[i][1])
if ans_first > ans_second:
break
i += 1
if ans_first <= ans_second:
res = ans_second - ans_first + 1
else:
x = Min
while x <= Max:
cnt = 0
i = 0
while i < n:
if a[i][0] <= x and x <= a[i][1]:
cnt += 1
if cnt > k:
break
i += 1
if cnt == k:
res += 1
x += 1
print(res)Với $K = N$ thì độ phức tạp thời gian chỉ là $O(N)$, không phụ thuộc $A$, $B$ lớn cỡ nào, chỉ lặp đúng $N$ lần là ra kết quả. Với độ phức tạp $O(N)$ được xem là tốt nhất này thì chắc chắn thỏa giới hạn 1 giây, tự tin lấy trọn 30% điểm hen các bạn.
Gộp xử lý K = N vào lúc đọc input
Ở trên mình tách quá trình input với xử lý ra riêng để các bạn nhìn cho rõ. Bản chất ta có thể xử lý $K = N$ ngay khi đọc input luôn, vì input là đọc từng đoạn thẳng vào mà. Từ đầu ta khởi tạo đoạn giao ans với ans.first = 0 và ans.second = 10^18 + 1, để khi so sánh với đoạn đầu tiên a[0] thì nó được cập nhật chính là a[0]:
max(ans.first, a[0].first)luôn làa[0].first, doans.first = 0đảm bảo nhỏ hơn mọia[i].first(đề cho các đoạn tối thiểu từ 1).min(ans.second, a[0].second)luôn làa[0].second, doans.second = 10^18 + 1đảm bảo lớn hơn mọia[i].second(đề cho tối đa $10^{18}$).
Xem code cách 6 (gộp K = N vào input)
#include <bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
long long n, k;
cin >> n >> k;
vector<pair<long long, long long>> a(n);
long long Max = LLONG_MIN, Min = LLONG_MAX;
pair<long long, long long> ans(0, 1000000000000000001LL);
bool check = true;
for(long long i = 0; i < n; ++i){
cin >> a[i].first >> a[i].second;
Min = min(Min, a[i].first);
Max = max(Max, a[i].second);
if(check == true){
ans.first = max(ans.first, a[i].first);
ans.second = min(ans.second, a[i].second);
if(ans.first > ans.second){
check = false;
}
}
}
long long res = 0;
if(k == n){
if(check == true){
res = ans.second - ans.first + 1;
}
}
else{
for(long long x = Min; x <= Max; ++x){
long long cnt = 0;
for(long long i = 0; i < n; ++i){
if(a[i].first <= x && x <= a[i].second){
cnt++;
if(cnt > k){
break;
}
}
}
if(cnt == k){
res++;
}
}
}
cout << res;
return 0;
}import sys
tokens = []
while len(tokens) < 2:
tokens += list(map(int, sys.stdin.readline().split()))
n, k = tokens[:2]
a = [None] * n
Max = -9223372036854775808
Min = 9223372036854775807
ans_first = 0
ans_second = 1000000000000000001
check = True
read = []
while len(read) < 2 * n:
read += list(map(int, sys.stdin.readline().split()))
for i in range(n):
first = read[2 * i]
second = read[2 * i + 1]
a[i] = (first, second)
Min = min(Min, first)
Max = max(Max, second)
if check:
ans_first = max(ans_first, first)
ans_second = min(ans_second, second)
if ans_first > ans_second:
check = False
res = 0
if k == n:
if check:
res = ans_second - ans_first + 1
else:
x = Min
while x <= Max:
cnt = 0
i = 0
while i < n:
if a[i][0] <= x and x <= a[i][1]:
cnt += 1
if cnt > k:
break
i += 1
if cnt == k:
res += 1
x += 1
print(res)+20%Lời giải 100%: chia đoạn + update đoạn
Để giải quyết trọn vẹn bài này mình dùng đến 2 kỹ thuật mà không có trong sách giáo khoa chuyên Tin hay những tài liệu phổ biến đâu, mình cũng tự nghiệm ra nó thông qua việc giải bài thôi 😀
Kỹ thuật 1: chia đoạn
Khi có $N$ đoạn $[l_1, r_1],$ $[l_2, r_2],$ $\ldots,$ $[l_N, r_N]$, ta cần chia chúng thành những đoạn con nhỏ rời rạc sao cho mỗi đoạn con hoặc là đoạn con của 1 hoặc nhiều đoạn, hoặc không là đoạn con của đoạn nào. Ví dụ 5 đoạn $[1, 9],$ $[3, 5],$ $[4, 13],$ $[7, 9],$ $[2, 15]$:
chia được thành các đoạn con:
Đây là những đoạn con hoàn toàn rời rạc. Ví dụ $[4, 5]$ là đoạn con của cả 5 đoạn trên, $[10, 13]$ là đoạn con của $[4, 13]$ và $[2, 15]$. Mục đích của việc chia này là bảo đảm các đoạn con rời nhau, và chỉ cần biết 1 phần tử của đoạn con có $K$ đoạn phủ lên thì cả đoạn con đó cũng có $K$ đoạn phủ lên.
Cách chia đoạn:
- Tạo vector
v, với mỗi đoạn $[l, r]$ đưa $l - 1$ và $r$ vào. Với ví dụ trên: $v = \{0, 9, 2, 5, 3, 13, 6, 9, 1, 15\}$. - Sắp xếp tăng dần: $\{0, 1, 2, 3, 5, 6, 9, 9, 13, 15\}$.
- Với 2 phần tử kề nhau $v[i]$ và $v[i + 1]$ thì $[v[i] + 1, v[i + 1]]$ là một đoạn con: $\{0, 1\} \to [1, 1]$, $\{1, 2\} \to [2, 2]$, $\{2, 3\} \to [3, 3]$, $\{3, 5\} \to [4, 5]$, $\{5, 6\} \to [6, 6]$, $\{6, 9\} \to [7, 9]$, $\{9, 13\} \to [10, 13]$, $\{13, 15\} \to [14, 15]$. Cặp $\{9, 9\}$ cho đoạn $[10, 9]$ rỗng nên bỏ qua.
Kỹ thuật 2: update đoạn (mảng sai phân)
Bài toán: cho $N$ đoạn thẳng, đoạn thứ $i$ phủ các điểm $[l_i .. r_i]$. Hỏi với mỗi điểm, có bao nhiêu đoạn thẳng phủ lên đó? Ví dụ $N = 5$: $[1 .. 5],$ $[4 .. 10],$ $[3 .. 8],$ $[10 .. 10],$ $[10 .. 12]$.
Gọi f[i] là số đoạn phủ lên điểm $i$, ban đầu toàn 0. Với đoạn $[l .. r]$ ta tăng f[l] lên 1 và giảm f[r + 1] xuống 1:
- $[1 .. 5]$: tăng f[1], giảm f[6]
- $[4 .. 10]$: tăng f[4], giảm f[11]
- $[3 .. 8]$: tăng f[3], giảm f[9]
- $[10 .. 10]$: tăng f[10], giảm f[11]
- $[10 .. 12]$: tăng f[10], giảm f[13]
Sau đó duyệt lại các vị trí, tính f[i] = f[i - 1] + f[i] (cộng dồn) là ra số đoạn phủ lên từng điểm:
| Điểm i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| f[i] sau khi cập nhật | 1 | 0 | 1 | 1 | 0 | -1 | 0 | 0 | -1 | 2 | -2 | 0 |
| f[i] sau cộng dồn | 1 | 1 | 2 | 3 | 3 | 2 | 2 | 2 | 1 | 3 | 1 | 1 |
Tức điểm 1 có 1 đoạn, điểm 3 có 2 đoạn, điểm 4 và 5 có 3 đoạn, điểm 10 có 3 đoạn, … đúng với các đoạn đề cho.
Ứng dụng 2 kỹ thuật vào bài
- Tạo bảng
fvới ý nghĩa tương tự:f[i]là số đoạn phủ lên điểm $i$. Do $i$ rất lớn ($1 \le l \le r \le 10^{18}$) nênfphải tổ chức bằngmap. - Với mỗi đoạn $[l .. r]$:
f[l]++vàf[r + 1]--. Sau đó cập nhật lại bảng bằng cách cộng dồnf[sau] = f[trước] + f[sau]. - Chia $N$ đoạn thành những đoạn rời rạc: tạo vector
savelưu $l - 1$ và $r$, rồi sort tăng dần. - Xét từng đoạn con $[L .. R]$ với $L$ =
save[i] + 1, $R$ =save[i + 1]. Nếuf[L] == Khoặcf[R] == Kthì đã có 1 điểm trong đoạn có $K$ đoạn phủ, nghĩa là toàn bộ đoạn con đều có $K$ đoạn phủ, ta cộngans += R - L + 1. - Đáp án là
ans.
Độ phức tạp thời gian là $O(N \log N)$, yên tâm không bị TLE và ăn trọn 100% điểm bài này.
Em nhập các đoạn (mỗi đoạn 2 số l r, các đoạn cách nhau dấu phẩy) và $K$ rồi bấm Tiếp để xem từng bước: cập nhật mảng sai phân f tại các mốc, rồi cộng dồn qua từng khúc và cộng độ dài những khúc có đúng $K$ đoạn phủ. Ô xanh ở hàng "phủ" là khúc được tính:
Source code để các bạn tham khảo với tất cả những gì mình phân tích ở trên:
#include <bits/stdc++.h>
using namespace std;
struct segment {
long long l, r;
};
vector <segment> listSegment;
int n, k;
map <long long, int> f;
void process() {
vector <long long> save;
vector <long long> listID;
for (int i = 0; i < n; i++) {
long long l = listSegment[i].l;
long long r = listSegment[i].r;
save.push_back(l - 1);
save.push_back(r);
f[l]++;
f[r + 1]--;
listID.push_back(l);
listID.push_back(r + 1);
}
sort(save.begin(), save.end());
sort(listID.begin(), listID.end());
for (int i = 1; i < (int) listID.size(); i++) {
if (listID[i] != listID[i - 1]) {
f[listID[i]] += f[listID[i - 1]];
}
}
long long ans = 0LL;
for (int i = 0; i < (int) save.size() - 1; i++) {
long long l = save[i] + 1;
long long r = save[i + 1];
if (l > r) {
continue;
}
if (f[l] == k || f[r] == k) {
ans += r - l + 1;
}
}
cout << ans;
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
segment myseg;
cin >> myseg.l >> myseg.r;
listSegment.push_back(myseg);
}
process();
return 0;
}import sys
class segment:
def __init__(self):
self.l = 0
self.r = 0
listSegment = []
f = {}
tokens = []
while len(tokens) < 2:
tokens += list(map(int, sys.stdin.readline().split()))
n, k = tokens[:2]
read = []
while len(read) < 2 * n:
read += list(map(int, sys.stdin.readline().split()))
for i in range(n):
myseg = segment()
myseg.l = read[2 * i]
myseg.r = read[2 * i + 1]
listSegment.append(myseg)
def process():
for seg in listSegment:
l = seg.l
r = seg.r
f[l] = f.get(l, 0) + 1
f[r + 1] = f.get(r + 1, 0) - 1
points = sorted(f.keys())
cur = 0
ans = 0
for i in range(len(points) - 1):
cur += f[points[i]]
if cur == k:
ans += points[i + 1] - points[i]
print(ans)
process()