传送门

CF1034D Intervals of Intervals

题目大意

有 \(n\) 个线段，第 \(i\) 个是 \([a_i,b_i]\)。

定义区间 \([l,r]\) 的价值是第 \(l\) 个线段到第 \(r\) 个线段的并的长度。

找出 \(k\) 个不同的区间，使得总价值最大。输出最大总价值。

\(1 \le n \le 3 \times 10^5,1 \le k \le \min\{ \frac{n(n+1)}{2},10^9 \},1 \le a_i < b_i \le 10^9\)。

思路

我们肯定会选出价值前 \(k\) 大的区间。因为 \(k\) 很大，所以我们可以尝试二分价值第 \(k\) 大的区间的价值。

我们设二分的值为 \(mid\)，那么问题就变为了求价值大于等于 \(mid\) 的区间个数。

要求解这个问题，我们肯定需要一种算法，能够处理到所有区间的价值。

因为是求线段并集，我们考虑转化为染色问题，第 \(i\) 个线段的颜色为 \(i\)，没有被染色的位置颜色是 \(0\)。

我们按 \(1\) 到 \(n\) 的顺序依次加入线段 \(r\)，那么对于任意 \(l\)，区间 \([l,r]\) 的价值就是当前颜色编号大于等于 \(l\) 的位置个数。

如果我们记录 \(c_l\) 为区间 \([l,r]\) 的价值，那么其实这就是一个 \(c\) 数组的区间加法。这可以使用树状数组直接维护。

因为染色的过程是区间赋值，可以使用 ODT 维护。

ODT（Old Driver Tree，俗称珂朵莉树），就是把具有相同值 \(x\) 的一段连续区间 \([l,r]\) 压成一个三元组 \((l,r,x)\)。三元组存入 set，维护区间修改时暴力合并分裂区间即可。

这样我们就用 \(O(n \log n)\) 的时间完成了所有区间价值的处理。

但是注意我们的问题是求价值大于等于 \(mid\) 的区间个数。

容易发现，区间的价值（设为 \(w_{l,r}\)）具有一定的单调性：\(w_{l,r} \ge w_{l+1,r},w_{l,r} \ge w_{l,r+1}\)。

也就是说，对于每个 \(r\)，如果区间 \([l,r]\) 满足条件，那么 \(\forall i < l\)，区间 \([i,r]\) 满足条件；且 \(r\) 单调递增时，\(l\) 单调不减。

所以我们可以使用双指针，找出最后一个价值大于等于 \(mid\) 的区间，这样我们就可以用 \(O(n \log n)\) 的时间统计区间个数。

所以我们的总体复杂度就可以做到 \(O(n \log n \log k)\)。

显然这样的复杂度是不能通过的。我们需要优化。

可以发现，其实我们可以只跑一次 ODT，记录修改操作。然后在二分 \(mid\) 时，用差分数组重做这些操作就好了，这样就少了一个 \(\log\)。

然后就做完了。复杂度 \(O(n \log n + n \log k)\)。

代码实现

可以把二分的 check 和求答案放在一起写。

注意变量名不要写错了。

check 的写法需要注意。

#include<bits/stdc++.h>
#define ll long long
#define For(i,a,b) for(ll i=(a);i<=(b);++i)
#define Rep(i,a,b) for(ll i=(a);i>=(b);--i)
#define pb push_back
const ll N=1e6+10;
using namespace std;

ll n,k;
ll a[N],b[N];//线段

struct node{
	ll l,r,c;
	bool operator<(const node&a)const{
		return l<a.l||l==a.l&&r<a.r;
	}
};
set<node>s;//ODT
vector<node>op[N];//记录原始的区间，用于覆盖的区间就是(a[i],b[i],i)，无需记录
void init(){
	s.insert({0,(ll)1e9,0});//一开始都是0
	For(i,1,n){
		auto it=s.lower_bound({a[i],(ll)1e9,0});//找到一条过点a[i]的色块
		--it;
		ll l=it->l,r=it->r,c=it->c;
		//整条线段被色块包含
		if(r>=b[i]){
			s.erase(it);
			op[i].pb({a[i],b[i],c});
			if(l<a[i])s.insert({l,a[i]-1,c});
			if(r>b[i])s.insert({b[i]+1,r,c});
			s.insert({a[i],b[i],i});
			continue;
		}
		//线段最左端的色块
		s.erase(it++);
		op[i].pb({a[i],r,c});
		if(l<a[i])s.insert({l,a[i]-1,c});
		//线段包含的色块
		while(it->r<b[i]){
			op[i].pb(*it);
			s.erase(it++);
		}
		//线段最右端的色块
		l=it->l,r=it->r,c=it->c;
		s.erase(it);
		op[i].pb({l,b[i],c});
		if(r>b[i])s.insert({b[i]+1,r,c});
		s.insert({a[i],b[i],i});
	}
}

ll ans;
ll d[N];//差分数组
ll check(ll mid){
	ans=0;//价值大于等于mid的区间价值和
	ll s=0;//差分数组L位置到R位置的总和
	ll now=0;//差分数组1位置到L-1位置代表的区间价值和
	ll res=0;//价值大于等于mid的区间数量
	ll L=1;//左端点
	For(R,1,n){//右端点
		d[R]=b[R]-a[R]+1;//预处理为长度
		s+=d[R];
		for(auto j:op[R]){
			ll l=j.l,r=j.r,c=j.c;
			d[c]-=r-l+1;//差分
			if(c>=L)s-=r-l+1;
			if(c&&c<L)now-=c*(r-l+1);
		}
		while(s>=mid){
			s-=d[L];
			now+=L*d[L];
			L++;//左端点移动
		}
		ans+=now+s*(L-1);//统计答案
		res+=L-1;//统计个数
	}
	ans-=mid*(res-k);//我们只需要求前k大的总和，多出来的区间减掉
	return res>=k;
}

void mian(){
	
    scanf("%lld%lld",&n,&k);
	For(i,1,n){
		scanf("%lld%lld",&a[i],&b[i]);
		b[i]--;//转成闭区间
	}
	init();
	ll l=0,r=1e9,len=0;
	while(l<=r){
		ll mid=l+r>>1;
		if(check(mid)){
			len=mid;
			l=mid+1;
		}else r=mid-1;
	}
	check(len);
	printf("%lld",ans);
	
}

int main(){
	int T=1;
//	scanf("%d",&T);
	while(T--)mian();
	return 0;
}

尾声

如果你发现了问题，你可以直接回复这篇题解

如果你有更好的想法，也可以直接回复！