0%

「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维护线段,本来就去写线段树了


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#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;
}