CF1034D Intervals of Intervals

题意：给定 \(N\) 条线段，定义一个区间的价值为区间线段并的长度，求前 \(K\) 大区间价值和。

题解：首先考虑一个简化版本，求区间线段并。

扫描线，维护每个左端点的答案。对于每个位置维护最后一次包含它的线段，把相邻相同的位置合并，用 \(\texttt{set}\) 维护这些连续段，复杂度是均摊的。

回到原题，考虑二分出 \(K\) 大值。令 \(L_i\) 表示以 \(i\) 为右端点时区间并 \(<M\) 的左端点，显然 \(L_i\) 单调不降。双指针的同时也可以维护出答案，详见代码。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
const int mod=1e9+7;
const int inf=1e9;
#define pb push_back
#define pii pair<int,int>
#define ll long long
#define lll __int128
#define fi first
#define se second
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
struct itv{
	int l,r,tg;
	bool operator<(const itv &x)const{
		return x.l^l?l<x.l:r<x.r;
	}
};set<itv>S;
inline void split(int p){
	if(!p)return;
	auto it=--S.lower_bound({p+1,0,0});
	if(it->r==p)return;
	S.insert({it->l,p,it->tg});
	S.insert({p+1,it->r,it->tg});
	S.erase(it);
}
int n,m;lll sum,cnt;
vector<pii>laz[maxn],buc[maxn];
inline bool chk(int mid){
	sum=cnt=0;ll cs=0,cur=0;
	for(int l=1,r=1;r<=n;r++){
		for(auto x:laz[r])if(x.fi<=l)
			cur+=x.se,cs+=1ll*x.se*(l-x.fi);
		while(cur>=mid){
			cs+=cur,++l;
			for(auto x:buc[l])
				if(x.fi<=r)cur+=x.se;
		}sum+=cs,cnt+=l-1;
	}return cnt>=m;
}
int main(){
	n=read(),m=read();
	S.insert({1,inf,0});
	for(int i=1,l,r;i<=n;i++){
		l=read(),r=read()-1;
		split(l-1),split(r);
		while(1){
			auto it=S.lower_bound({l,0,0});
			if(it==S.end()||it->l>r)break;
			int las=it->tg,len=it->r-it->l+1;
			laz[i].pb({las+1,len});
			laz[i].pb({i+1,-len});
			buc[las+1].pb({i,len});
			buc[i+1].pb({i,-len});
			S.erase(it); 
		}S.insert({l,r,i});
	}int l=1,r=inf,kth=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(chk(mid))kth=mid,l=mid+1;
		else r=mid-1;
	}chk(kth);
	printf("%lld\n",(ll)(sum-(cnt-m)*kth));
	return 0;
}

原文地址：http://www.cnblogs.com/syzf2222/p/16910204.html