总结
一种经典的题型，诸如区间合并，区间选择等
区间合并
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| vector<PII> q;
for(int i=1;i<=n;i++){
cin>>a[i]>>b[i];
mx=max({mx,a[i],b[i]});
if(a[i]>=b[i]){
mn=min(mn,b[i]);
q.pb({b[i],a[i]});
}
}
sort(all(q));
vector<PII> s;
for(auto [l,r] : q){
if(!s.empty()&&l<=s.back()[1]){
s.back()[1]=max(s.back()[1],r);
}else{
s.push_back({l,r});
}
}
|
智乃的k线段区间
地址
先预处理出所有“包含K条线段”的最小区间
利用 map 对 key 的排序使右端点有序，再分别把 l 放入 multiset 使左端点有序
保证 multiset 的大小为 k，此时的左右端点即为最小区间
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| void solve()
{
int n,m,k;
cin>>n>>m>>k;
map<int,vector<int>> mp;
for(int i=1;i<=n;i++){
int l,r;
cin>>l>>r;
mp[r].push_back(l);
}
multiset<int> s;
ll ans=0;
int left=1;
for(auto [r,v] : mp){
for(auto l:v){
s.insert(l);
}
while(s.size()>k){
s.erase(s.begin());
}
if(s.size()==k){
int tp=*s.begin();
ans+=(tp-left+1)*(m-r+1);
left=tp+1;
}
}
cout<<ans<<'\n';
}
|