「Codeforces 1034D」Intervals of Intervals

zx2003说多 log 过不去，不然就去写了

Codeforces 1034D

题意

你有 \(n\) 个区间 \([a_i, b_i]\)，定义区间的区间 \([l,r]\) 的价值是第 \(l\) 个区间到第 \(r\) 个区间的并的总长度

你需要找出 \(k\) 个不同的区间的区间，使得它们的总价值最大

输出总价值

\(1\le n \le 3 * 10^5,1 \le k \le \min\{\frac{n(n+1)}{2},10^9\}\)

---

做法

显然我们要选出最大的 \(k\) 个区间的区间

显然可以二分其中最小的一个的价值

显然对于一个 \(r\)，满足价值不小于常数 \(x\) 的区间的区间 \([l,r]\) 的可能的 \(l\) 是一个前缀

显然单调增加 \(r\)，最大的 \(l\) 是单调的

考虑用平衡树维护线段及编号，并记录每条线段剩余未被覆盖的长度，加入线段时把覆盖的部分删除即可

这样就可以维护一个 \(l\) 的最大值，单次 \(\mathcal O(n\log n\log w)\)，其中 \(w\) 是值域

但是显然这里删除和插入线段的总次数是 \(\mathcal O(n)\) 的，于是我们可以只做一次，记录每次删除的情况，之后可以单次 \(\mathcal O(n)\) 地检验一个答案

以上复杂度 \(\mathcal O(n(\log n+\log w))\)

还有一个问题是要求出最大的 \(k\) 个区间的区间的价值和

和单次的检验一样，也是维护每条线段未被覆盖的长度

记当前右端点是 \(r\)，可行的 \(l\) 的最大值为 \(max_l\)

对于 \([max_l,r]\) 之间的线段，贡献 \(max_l\) 次，对于 \(i>max_l\) 贡献 \(i\) 次

简单维护一下就好了

这里未被覆盖的长度就可以避免重复计算

注意选出的区间的区间不一定是恰好 \(k\) 个，但是多出的部分价值必然是二分出来的价值，减去就好了

由于当价值相同的区间的区间很多的时候，计算出来的总贡献应该会爆long long，但是答案是不会爆的，减去之后会自然溢出回来，所以直接写就好了

排斥set维护线段，本来就去写线段树了

---

代码

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<set>
#include<vector>

using namespace std;
#define ll long long
#define pb push_back

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig=false, c=read(); !isdigit(c); c=read()) {
		if (c == '-') iosig=true;
		if (c == -1) return;
	}
	for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
	if (iosig) x=-x;
}

const int N = 300005, inf = 1e9+1;
int mx, n, k, id, a[N], b[N], len[N];
struct seg{
	int l, r, col;
	inline bool operator <(const seg &rhs)const{ return l<rhs.l || (l==rhs.l && r<rhs.r);}
};
set<seg> s;
vector<seg> e[N];
inline void init(){
	s.insert((seg){0, inf, 0});
	for(int i=1; i<=n; ++i){
		auto it=s.lower_bound((seg){a[i], inf, 0});
		--it;
		if(it->r >= b[i]){
			e[i].pb((seg){a[i], b[i], it->col});
			if(it->l < a[i]) s.insert((seg){it->l, a[i]-1, it->col});
			if(it->r > b[i]) s.insert((seg){b[i]+1, it->r, it->col});
			s.erase(it);
			s.insert((seg){a[i], b[i], i});
			continue;
		}
		e[i].pb((seg){a[i], it->r, it->col});
		if(it->l < a[i]) s.insert((seg){it->l, a[i]-1, it->col});
		s.erase(it++);
		if(it->r<a[i]) ++it;
		while(it->r < b[i]) e[i].pb(*it), s.erase(it++);
		e[i].pb((seg){it->l, b[i], it->col});
		if(it->r > b[i]) s.insert((seg){b[i]+1, it->r, it->col});
		s.erase(it);
		s.insert((seg){a[i], b[i], i});
	}
}
inline bool check(int x){
	int sum=0;
	ll cnt=0;
	for(int i=1, l=1; i<=n; ++i){
		sum+=(len[i]=b[i]-a[i]+1);
		for(auto j:e[i]){
			len[j.col]-=j.r-j.l+1;
			if(j.col && j.col>=l) sum-=j.r-j.l+1;
		}
		while(sum>=x) sum-=len[l], ++l;
		cnt+=l-1;
	}
	return cnt>=k;
}
inline ll solve(int x){
	int sum=0;
	ll ans=0, cnt=0, now=0;
	for(int i=1, l=1; i<=n; ++i){
		sum+=(len[i]=b[i]-a[i]+1);
		for(auto j:e[i]){
			len[j.col]-=j.r-j.l+1;
			if(j.col && j.col>=l) sum-=j.r-j.l+1;
			if(j.col && j.col<l) now-=(ll)j.col*(j.r-j.l+1);
		}
		while(sum>=x) sum-=len[l], now+=(ll)l*len[l], ++l;
		ans+=now+(ll)sum*(l-1);
		cnt+=l-1;
	}
	return ans-(ll)(cnt-k)*x;
}
int main() {
	read(n), read(k);
	for(int i=1; i<=n; ++i) read(a[i]), read(b[i]), --b[i];
	init();
	int l=1, r=1e9, ans=0;
	while(l<=r){
		int mid=(l+r)/2;
		if(check(mid)) l=mid+1, ans=mid; else r=mid-1;
	}
	return printf("%lld", solve(ans)), 0;
}