题解：P16348 「MierOI R1」Eternal (Hard ver.)
lailai0916
·
·
题解
题意简述
给定若干个闭区间。
选出尽可能多的区间，要求：
任意两个相交的已选区间，
至少有一个端点相同。
解题思路
先单独记录退化区间 [i,i] 的数量 c_i。
其余区间都满足 l<r。
记 f_i 为只使用端点不超过 i 的区间时，
最多可以选择多少个区间。
两个合法方案可以在坐标 i 处拼接。
左侧区间的右端点不超过 i，
右侧新增区间的左端点不小于 i。
若它们相交，交集只能是共同端点 i。
下面只考虑右端点为 i 的新方案。
若没有选择任何右端点为 i 的非退化区间，
可以直接从 f_{i-1} 转移。
否则，设这些区间的最小左端点为 l。
于是，至少选择了一份最外层区间 [l,i]。
考虑任何无法放入旧方案 f_l 的区间。
它的内部必须与 [l,i] 相交。
为了满足题意，它必须与 [l,i] 共用端点。
所以，这些新增区间只有两类：
- 左端点为 l 的区间 [l,x]
- 右端点为 i 的区间 [y,i]
左侧区间 [l,x] 与右侧区间 [y,i] 合法，
当且仅当 x\le y。
因此，存在一个分界坐标 k，满足：
x\le k\le y
先处理只选择一类区间的情况。
若新增区间都共用左端点 l，
可以把当前所有右端点不超过 i 的 [l,x] 加入。
对应值为：
f_l+\#\{[l,x]\mid x\le i\}
扫描 i 时，
每遇到一份 [l,i]，就把位置 l 的值加一。
代码用大根堆维护所有位置的当前值。
修改后压入新值，查询时丢弃过期记录。
若新增区间都共用右端点 i，
枚举其中最小的左端点 l。
排序后缀中的全部区间都可以选择，转移为：
f_l+\#\{[x,i]\mid x\ge l\}
最后处理左右两类区间同时存在的情况。
设 w(l,i) 是区间 [l,i] 的重数。
固定分界点 k，
最外层区间之外的可选数量为：
F(k)=\#\{[l,x]\mid x<i,x\le k\}+\#\{[y,i]\mid y>l,y\ge k\}
于是，对固定的 l,i，候选答案为：
f_l+w(l,i)+\max_{l<k\le i}F(k)
记 R_l 为左端点是 l 的右端点列表，
记 L_i 为右端点是 i 的左端点列表。
两个列表均保留重复元素并排序。
第二项只会在 $L_i$ 中的坐标减少。
若枚举 $R_l$，
相邻变化点之间第一项不变，第二项单调不增。
区间最大值一定在左端取得。
若枚举 $L_i$，
相邻变化点之间第二项不变，第一项单调不减。
区间最大值一定在右端取得。
所以，只需枚举 $R_l,L_i$ 中较短的列表。
另一项可以通过二分统计。
两侧边界再各检查一次即可。
处理完非退化区间后，
把全部 $[i,i]$ 加入答案。
它们与旧区间至多在端点 $i$ 相交，
所以一定可以全部选择。
下面估计枚举较短列表的总代价。
把每个不同的非退化区间看作一条边。
端点的度数按区间重数计算。
每条边的代价不超过两端度数的较小值。
把边朝度数较大的端点定向。
度数为 $d$ 的点至多连向 $d$ 个不同点。
它也至多连向 $2m/d$ 个度数不小于它的点。
因此，该点承担的代价至多为：
$$
d\min\left(d,\frac{2m}{d}\right)
$$
分别考虑 $d\le\sqrt m$ 与 $d>\sqrt m$。
对全部端点求和可得 $O(m\sqrt m)$。
每次枚举还需进行二分。
所以，总时间复杂度为 $O(n\sqrt n\log n)$。
空间复杂度为 $O(n)$。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
vector<int> lft[N],rgt[N];
int cnt[N],f[N],g[N];
int calc(int k,int l,int r)
{
int x=upper_bound(rgt[l].begin(),rgt[l].end(),min(k,r-1))-rgt[l].begin();
int y=lft[r].end()-lower_bound(lft[r].begin(),lft[r].end(),k);
return x+y;
}
void solve()
{
int n;
cin>>n;
int m=2*n;
for(int i=1;i<=n;i++)
{
int l,r;
cin>>l>>r;
if(l==r)cnt[l]++;
else
{
lft[r].push_back(l);
rgt[l].push_back(r);
}
}
for(int i=1;i<=m;i++)
{
sort(lft[i].begin(),lft[i].end());
sort(rgt[i].begin(),rgt[i].end());
}
priority_queue<pair<int,int>> h;
for(int i=1;i<=m;i++)
{
for(int l:lft[i])
{
g[l]++;
h.push({g[l],l});
}
while(!h.empty()&&h.top().first!=g[h.top().second])h.pop();
int ans=f[i-1];
if(!h.empty())ans=max(ans,h.top().first);
int s=lft[i].size();
for(int j=0;j<s;)
{
int l=lft[i][j];
int p=upper_bound(lft[i].begin()+j,lft[i].end(),l)-lft[i].begin();
ans=max(ans,f[l]+s-j);
int val=0;
if(rgt[l].size()<lft[i].size())
{
val=calc(l+1,l,i);
for(int k:rgt[l])if(l<k&&k<i)val=max(val,calc(k,l,i));
}
else
{
val=calc(i,l,i);
for(int k:lft[i])if(l<k&&k<=i)val=max(val,calc(k,l,i));
}
ans=max(ans,f[l]+p-j+val);
j=p;
}
f[i]=ans+cnt[i];
g[i]=f[i];
h.push({g[i],i});
}
cout<<f[m]<<'\n';
for(int i=0;i<=m;i++)
{
lft[i].clear();
rgt[i].clear();
cnt[i]=f[i]=g[i]=0;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin>>t;
while(t--)solve();
return 0;
}
```