CF1034D
总评：非常牛逼的 \(3500\)。
求第 \(k\) 大的价值可以二分一个 \(m\)，变成求价值 \(\ge m\) 的区间个数，设其为 \(C(m)\)。求出第 \(k\) 大价值 \(M\) 后，本题求前 \(k\) 大的价值和，这便要求我们求价值 \(\ge m\) 的区间价值和，记为 \(S(m)\)。容易知道答案为 \(S(M)-(C(M)-k)M\)。
区间形如 \([l,r]\)，最外层是二分只有单 \(\log\)，因此有线性以上时间供我们求出 \(C(m)\) 或 \(S(m)\)。对 \(r\) 做扫描线，从小到大枚举 \(r\)，此时，对于每一个 \(l\) 都维护区间 \([l,r]\) 的价值，记为 \(f_l\)。
我们发现，对于确定的 \(r\)，\(f_l\) 随 \(l\) 的增加而单调不增，因为 \(l\gets l-1\) 相当于并上一个新线段，不会使 \(f\) 变小。因此维护一个指针 \(p_r\)，表示：\(\forall l\le p_r\)，\([l,r]\) 的价值 \(f_l \ge m\)；\(\forall l>p_r\)，\([l,r]\) 的价值 \(f_l<m\)。那么这个 \(r\) 对 \(C(m)\) 的贡献为 \(p_r\)，对 \(S(m)\) 的贡献为 \(\sum_{l\le p_r} f_l\)。
现在考虑，\(r\gets r+1\) 会对 \(f\) 序列和 \(p_r\) 产生什么影响。线段交这个东西难做，考虑维护一条数轴，把问题转化为：观察每个整点是否被 \(i\in [l,r]\) 的线段 \([a_i,b_i)\) 覆盖。
这一步，我们对数轴上的整点 \(k\) 维护 \(\operatorname{lst}_k\) 表示覆盖它的线段中标号 \(i\) 的最大值，即它最晚是被哪条线段覆盖的。有 \(f_l=\sum_{k}[\operatorname{lst}_k\ge l]\)；将线段 \([a_r,b_r)\) 覆盖上去，等价于 \(\forall k\in[a_r,b_r),\operatorname{lst}_k=r\)，那么 \(\forall k\in[a_r,b_r),l\in (\operatorname{lst}_k,r]\)，\(f_l\) 都要自增 \(1\)，因为 \(k\) 这个点新产生了贡献。这是区间加的形式。
观察 \(\forall k\in[a_r,b_r),\operatorname{lst}_k=r\)，我们知道这是区间推平。\(k\) 是 \(10^9\) 级别，所以使用珂朵莉树，维护 \(\operatorname{lst}\) 相同的子段。\(f\) 的区间加照做，只是数值上变成了 set 维护的子段长度而已。
同时，\(p_r\) 随 \(r\) 的增加单调不降，证明参考 \(f_l\) 的单调性。所以我们需要一种维护 \(f_l\) 的 DS，支持区间加，每次单点查询 \(f_{p_r+1}\) 的值，不断让 \(p_r\gets p_r+1\) 直到 \(f_{p_r+1}<m\) 即可。此时 \(S(m)\) 要求查询 \(\sum_{l\le p_r}f_l\)，区修区查，使用线段树可以得到总计 \(\mathcal O(n\log n)\) 的实现，只需调用一次。而 \(C(m)\) 外面有一层二分，\(\mathcal \Theta(n\log^2 n)\) 的复杂度难以承受，却不要求区间查询。
考虑 \(\mathcal O(n)\) 实现 \(C(m)\)。区修单查想到差分，令 \(d_l=f_l-f_{l-1}\)，区间加操作变成了 \(d_a\) 加上一个正数，\(d_{b+1}\) 减去一个正数。观察 \(p_r\) 的定义：\(\max\{p:\sum_{l\le p}d_l\ge m\}\)。维护 \(s=\sum_{l\le p_r} d_l\)，每次 \(p_r\) 右移时 \(s\gets s+d_{p_r+1}\) 即可。一个问题是 \(a\le p_r\) 时怎么办。因为加的是正数，所以 \(p_r\) 不会向左回退，直接加到 \(s\) 上就好了。这样就规避掉了 \(\log\) 数据结构。
可是 ODT 的 set 自带一个 \(\log\) 啊。这个不要紧，注意到每次二分出 \(m\)，要做的所有区间加操作都是固定的，和 \(m\) 无关。因此可以在二分前用 ODT 统一跑一次，处理出所有区间加，二分过程中就无需 ODT 了。
总复杂度 \(\mathcal O(n\log n)\)。注意 \(S(M)\) 与 \((C(M)-k)M\) 都可能非常大（\(\Theta(n^2|V|),10^{19}\)），需要 __int128。
#include <cstdio>
#include <cstring>
#include <vector>
#include <set>
#define ll long long
#define i3 __int128
using namespace std;
void re(int &x){
x=0;char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();
}
void wr(i3 n){
char st[40];int tp=0;
while(n) st[++tp]=n%10+48,n/=10;
while(tp) putchar(st[tp--]);
}
const int N=314514;
namespace sgt{
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
struct node{
int l,r;ll s,tg;
#define l(x) t[x].l
#define r(x) t[x].r
#define s(x) t[x].s
#define tg(x) t[x].tg
}t[N<<2];
void ad(int x,ll d){
s(x)+=1ll*d*(r(x)-l(x)+1);tg(x)+=d;
}
void downtag(int x){if(tg(x)) ad(ls(x),tg(x)),ad(rs(x),tg(x)),tg(x)=0;}
void updata(int x){s(x)=s(ls(x))+s(rs(x));}
void build(int now,int ln,int rn){
l(now)=ln;r(now)=rn;
if(ln==rn) return ;
int mid=ln+rn>>1;
build(ls(now),ln,mid);
build(rs(now),mid+1,rn);
updata(now);
}
void upd(int now,int l,int r,int x){
if(l<=l(now)&&r(now)<=r) return ad(now,x);
downtag(now);int mid=l(now)+r(now)>>1;
if(l<=mid) upd(ls(now),l,r,x);
if(r>mid) upd(rs(now),l,r,x);
updata(now);
}
ll qry(int now,int l,int r){
if(l<=l(now)&&r(now)<=r) return s(now);
downtag(now);int mid=l(now)+r(now)>>1;ll res=0;
if(l<=mid) res+=qry(ls(now),l,r);
if(r>mid) res+=qry(rs(now),l,r);
return res;
}
}
struct upd{int l,x;};
vector<upd> vc[N];
namespace ODT{
struct node{
int l,r;mutable int v;
bool operator<(const node &x)const{return l<x.l;}
};
set<node> st;
set<node>::iterator div(int pos){
auto p=st.lower_bound((node){pos});
if(p!=st.end()&&p->l==pos) return p;
--p;int l=p->l,r=p->r,v=p->v;st.erase(p);
st.insert((node){l,pos-1,v});
return st.insert((node){pos,r,v}).first;
}
void asn(int pos,int l,int r,int x){
auto pr=div(r+1),pl=div(l);
for(auto p=pl;p!=pr;++p) vc[pos].push_back((upd){p->v+1,p->r-p->l+1});
st.erase(pl,pr);st.insert((node){l,r,x});
}
}using namespace ODT;
int d[N],n;
ll calc_C(int m){//O(n)
memset(d,0,sizeof(d));
ll res=0;int cuf=0;
for(int l=1,r=1;r<=n;++r){
for(upd u:vc[r]){
if(r<n) d[r+1]-=u.x;
u.l<=l?cuf+=u.x:d[u.l]+=u.x;
}
while(l<=r&&(cuf>=m||!l)) cuf+=d[++l];
if(l) cuf-=d[l],--l;res+=l;
}
return res;
}
i3 calc_S(int m){//O(n log n)
i3 res=0;
for(int l=1,r=1;r<=n;++r){
for(upd u:vc[r]) sgt::upd(1,u.l,r,u.x);
while(l<=r&&(!l||sgt::qry(1,l,l)>=m)) ++l;
if(l) --l;if(l) res+=sgt::qry(1,1,l);
}
return res;
}
int a[N],b[N];
int main()
{
int k;re(n);re(k);sgt::build(1,1,n);
for(int i=1;i<=n;++i) re(a[i]),re(b[i]);
st.insert((node){1,n,0});
for(int r=1;r<=n;++r) asn(r,a[r],b[r]-1,r);
int l=1,r=1e9,val;while(l<=r){
int mid=(l+r)>>1;
calc_C(mid)>=k?(val=mid,l=mid+1):r=mid-1;
}
wr(calc_S(val)-(i3)(calc_C(val)-k)*val);
}
//To make this piece of code different from before