博主的 ( m bibi) 时间
“不会还有人不知道区间 ([l,r]) 的长度是 (r-l) 吧？”
题目
解法
还是来理一理思路吧。
先考虑弱化版：询问在 ([l,r]) 中线段的并的长度。
按 (1) 到 (n) 的顺序加入线段，用 set 来维护。需要维护三个值 ((l,r,t))，其中 (l,r) 是线段端点，(t) 是 最新 覆盖此区间的编号。需要注意的是，当 (t) 相等时必须保证线段不相交。
有什么用呢？实际上我们预先按顺序加入线段，用 vector 存储每个时间包含的线段（还需要存储上一个时间戳）。将询问按右端点排序，假设当前询问为 ([l,r])，则计算第 (r) 个时间对应的线段。那么 (le r) 的条件一定满足，于是定义 (f(i)) 为时间戳 (ge i) 的线段并长度。思考一下线段 ([L,R]) 的时间戳从 (t) 变到 (t') 会有什么影响：对于 (iin [t+1,t']) 的 (f(i)) 都加上了 (R-L)。这个可以差分一下。
如果强制在线呢？将差分数组改成线段树，再可持久化一下即可。
回到这道题，我们要求前 (k) 大区间的权值和（权值定义为线段的并的长度）。可以考虑二分第 (k) 大区间的权值，设当前二分到 ( m mid)，那么问题转化为查询权值 (ge m mid) 的区间的个数与权值和。需要注意的是可能有多个权值为第 (k) 大的区间，但由于已经知道这些区间的权值与个数，减去即可。另：如果查询权值 (> m mid) 的区间的话，(k-1) 可能等于 (0)，二分就会不停往大分。
在检验函数中，你会发现大区间的权值一定比它包含的小区间的权值大。基于此就可以用 ( ext{two-pointers}) 查询权值 (ge m mid) 的区间：(r) 右移，计算第 (r) 个时间对应的线段。维护 (l) 为此情况下权值 (ge m mid) 的最大左端时间，那么 ([1,l]) 都是合法的。
还有一些细节，代码加了注释。
代码
#include <bits/stdc++.h>
using namespace std;
#define rep(i,_l,_r) for(signed i=(_l),_end=(_r);i<=_end;++i)
#define fep(i,_l,_r) for(signed i=(_l),_end=(_r);i>=_end;--i)
#define erep(i,u) for(signed i=head[u],v=to[i];i;i=nxt[i],v=to[i])
#define efep(i,u) for(signed i=Head[u],v=to[i];i;i=nxt[i],v=to[i])
#define print(x,y) write(x),putchar(y)
#define debug(...) do {cerr<<__LINE__<<" : ("#__VA_ARGS__<<") = "; Out(__VA_ARGS__); cerr<<flush;} while(0)
template <typename T> void Out(T x) {cerr<<x<<"
";}
template <typename T,typename ...I> void Out(T x,I ...NEXT) {cerr<<x<<", "; Out(NEXT...);}
template <class T> inline T read(const T sample) {
T x=0; int f=1; char s;
while((s=getchar())>'9'||s<'0') if(s=='-') f=-1;
while(s>='0'&&s<='9') x=(x<<1)+(x<<3)+(s^48),s=getchar();
return x*f;
}
template <class T> inline void write(const T x) {
if(x<0) return (void) (putchar('-'),write(-x));
if(x>9) write(x/10);
putchar(x%10^48);
}
typedef long long ll;
typedef pair <ll,ll> pii;
#define int long long
const int maxn=3e5+5;
int n,m;
ll add[maxn];
struct node {
int l,r,t;
bool operator < (const node fk) const {
return l<fk.l;
}
};
set <node> s;
vector <pii> g[maxn];
typedef set <node> :: iterator Type;
Type split(int x) {
Type it=s.lower_bound((node){x,0,0});
if(s.end()!=it and it->l==x) return it;
--it;
if(it==s.end() or it->r==x) return s.end();
node tmp=*it;
s.erase(it);
s.insert((node){tmp.l,x,tmp.t});
return s.insert((node){x,tmp.r,tmp.t}).first;
}
pii ask(int x) {
pii tt,ret; int L=0;
ll sum=0,tmp=0;
rep(i,1,n) add[i]=0;
rep(i,1,n) {
for(int j=0;j<g[i].size();++j) {
tt=g[i][j];
/*
当 L>=tt.first 则 [tt.first,L] 一定满足条件，先加入 sum，为避免重复不加入差分数组
*/
if(tt.first>L)
add[tt.first]+=tt.second;
else {
tmp+=tt.second;
sum+=1ll*tt.second*(0ll+L-tt.first+1);
}
add[i+1]-=tt.second;
}
while(L+1<=i and tmp+add[L+1]>=x) {
tmp+=add[L+1];
sum+=tmp; ++L;
}
ret.first+=L,ret.second+=sum;
}
return ret;
}
signed main() {
n=read(9),m=read(9);
s.insert((node){0,(int)1e9,0});
rep(i,1,n) {
int a=read(9),b=read(9);
Type L=split(a),R=split(b);
while(L!=R) {
g[i].push_back(make_pair(L->t+1,L->r-L->l));
s.erase(L++);
}
s.insert((node){a,b,i});
}
int l=0,r=1e9,mid; pii ret;
while(l<r) {
mid=l+r+1>>1;
ret=ask(mid);
if(ret.first>=m) l=mid;
else r=mid-1;
}
ret=ask(l);
print(ret.second-1ll*(ret.first-m)*l,'
');
return 0;
}