题目描述
\(T\) 组数据，给定 \(n\) 条线段 \([l_i,r_i]\) ，称一个线段集合是复杂的，当且仅当：
- 它可以被划分成若干个大小相等的线段组。
- 两条线段相交当且仅当它们在同一组。
求用这 \(n\) 条线段构成的复杂线段集合的最大值。
数据范围
- \(1\le n,\sum n\le 3\cdot 10^5\) 。
- \(1\le l_i\le r_i\le 2n\) 。
分析
记 \(f(m)\) 为线段组大小为 \(m\) 时的最大组数，目标是求 \(m\cdot f(m)\) 的最大值。
显然 \(f(m)\le\lfloor\frac nm\rfloor\) 且单调递减，于是本质不同的 \(f(m)\) 只有 \(\mathcal O(\sqrt n)\) 种。接下来是经典的分治做法求所有 \(f(m)\) ：
void solve(int l,int r,int L,int R)
{
if(l>r) return ;
if(L==R)
{
for(int i=l;i<=r;i++) f[i]=l;
return ;
}
int mid=(l+r)>>1,val=calc(mid);
f[mid]=val;
solve(l,mid-1,L,val);
solve(mid+1,r,val,R);
}
对于本题，将所有线段按照右端点从小到大扫描，维护每个位置被几条线段覆盖，线段树维护区间加区间 \(\max\) ，可以做到 \(\mathcal O(n\log n)\) 计算单个 \(f(m)\) 的值。
至此 \(\mathcal O(n\sqrt n\log n)\) 已经可以通过 \(\texttt{E1}\) 了，接下来是人类智慧。
先用基数排序操作一下，使得所有端点互不相同。
维护被覆盖次数为后缀 \(\max\) 的所有下标 \(q_1,\cdots,q_k\) ，那么 \(q_i\) 被覆盖次数为 \(k+1-i\) 。
每次插入一条线段 \([l,r]\) ，我们将 \(r\) 加入下标集合，并删除 \(l\) 之前的最小下标。
并查集中 \(f_i\) 指向 \(i\) （含）前面最后一个在 \(q_1,\cdots,q_k\) 中的点即可。
时间复杂度 \(\mathcal O(n\sqrt n\alpha(n))\) 。
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pii pair<int,int>
using namespace std;
const int maxn=6e5+5;
int n,t,res;
int c[maxn],f[maxn];
pii p[maxn];
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
int calc(int m)
{
int cnt=0;
for(int i=1,x=0,cur=0,lim=0,lst=0;i<=n;i++)
{
int l=p[i].fi,r=p[i].se;
if(l<=lim) continue;
for(int j=lst+1;j<r;j++) f[j]=lst;
cur++,lst=f[r]=r,x=find(l);
if(x>lim) cur--,f[x]=x-1;
if(cur==m) cnt++,cur=0,lim=r;
}
res=max(res,cnt*m);
return cnt;
}
void solve(int l,int r,int L,int R)
{
if(l>r||L==R) return ;
int mid=(l+r)>>1,val=calc(mid);
solve(l,mid-1,L,val),solve(mid+1,r,val,R);
}
int main()
{
for(scanf("%d",&t);t--;)
{
scanf("%d",&n),memset(c,0,8*n),res=0;
for(int i=1;i<=n;i++) scanf("%d",&p[i].fi),c[p[i].fi]++;
for(int i=1;i<=n;i++) scanf("%d",&p[i].se),c[p[i].se]++;
for(int i=1;i<=2*n;i++) c[i]+=c[i-1];
for(int i=1;i<=n;i++) p[i].se=c[p[i].se]--;
for(int i=1;i<=n;i++) p[i].fi=c[p[i].fi]--;
sort(p+1,p+n+1,[&](pii x,pii y){return x.se<y.se;});
solve(1,n,n+1,0);
printf("%d\n",res);
}
return 0;
}