Educational Codeforces Round 69 (Rated for Div. 2) E. Culture Code
题意：
给出\(n\)个俄罗斯套娃，每个套娃都有一个\(in_i,out_i\)，并满足\(out_i>in_i\)。定义套娃\(i\)能套在套娃\(j\)里面，当且仅当\(out_i\leq in_j\)。
定义极大套娃组：当且仅当不能有另外一个套娃套在它们身上。
定义套娃组额外空间为\(in_1+(in_2-out_1)+\cdots +(in_k-out_{k-1})\)，其中\(k\)为最大的那个套娃。
现在求额外空间最小的极大套娃组都多少个。
思路：
将上面求和式子变换一下有：
\[in_k+\sum_{i=1}^{k-1}in_i-out_i
\]
\]
分析这个式子，也就是对于一个在最外面的套娃\(k\)来说，其余里面套娃的贡献就为\(in_i-out_i\)，是独立的。
首先将所有套娃按\(in\)升序排序，之后依次枚举每一个套娃并将其视作最后一个套娃。假设当前枚举的\(i\)，那么\(dp(i)=min_{out_j\leq in_i}\{dp(j)\}+in_i\)，\(dp\)中存储的是套娃的贡献值，\(dp(i)\)表示以\(i\)作结尾的套娃最小的额外空间是多少。
因为题目还要求数目，考虑转移的时候在线段树上面查询，同时维护一个\(sum\)记录个数，查询、更新的时候进行结点的合并，合并实现两个功能：一是找最小值，而是更新个数，详见代码即可。
最后统计答案的时候，找到所有的极大套娃组进行统计。
代码如下：
#include <bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int N = 2e5 + 5, MOD = 1e9 + 7;
int n;
pii a[N];
struct SEG{
struct node{
ll Min, sum;
node() {
sum = 0; Min = INF;
}
node(ll Min, ll sum) : Min(Min), sum(sum) {}
node operator + (const node &other) const {
node res = node();
if(Min < other.Min) {
res.Min = Min;
res.sum = sum;
} else if(Min == other.Min) {
res.Min = Min;
res.sum = (other.sum + sum) % MOD;
} else {
res.Min = other.Min;
res.sum = other.sum;
}
return res;
}
}t[N << 3], res;
void build(int o, int l, int r) {
if(l == r) {
t[o] = node();
return;
}
int mid = (l + r) >> 1;
build(o << 1, l, mid); build(o << 1|1, mid + 1, r);
}
void update(int o, int l, int r, int p, node v) {
if(l == r) {
t[o] = t[o] + v;
return ;
}
int mid = (l + r) >> 1;
if(p <= mid) update(o << 1, l, mid, p, v);
else update(o << 1|1, mid + 1, r, p, v);
t[o] = t[o << 1] + t[o << 1|1];
}
void query(int o, int l, int r, int L, int R) {
if(L <= l && r <= R) {
res = res + t[o];
return ;
}
int mid = (l + r) >> 1;
if(L <= mid) query(o << 1, l, mid, L, R);
if(R > mid) query(o << 1|1, mid + 1, r, L, R);
}
}seg;
int D, b[N << 1];
ll c[N], d[N];
int id(int x) {
return lower_bound(b + 1, b + D + 1, x) - b;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i].se >> a[i].fi;
b[++D] = a[i].fi; b[++D] = a[i].se;
}
sort(a + 1, a + n + 1);
sort(b + 1, b + D + 1);
D = unique(b + 1, b + D + 1) - b - 1;
ll Min = INF;
seg.build(1, 1, D);
for(int i = 1; i <= n; i++) {
seg.res = SEG::node();
seg.query(1, 1, D, 1, id(a[i].fi));
if(seg.res.Min == INF) {
seg.res = SEG::node(a[i].fi - a[i].se, 1);
c[i] = 1; d[i] = a[i].fi;
seg.update(1, 1, D, id(a[i].se), seg.res);
} else {
c[i] = seg.res.sum;
d[i] = seg.res.Min + a[i].fi;
seg.res.Min += a[i].fi - a[i].se;
seg.update(1, 1, D, id(a[i].se), seg.res);
}
if(a[i].se > a[n].fi) Min = min(Min, d[i]);
}
ll ans = 0;
for(int i = 1; i <= n; i++)
if(a[i].se > a[n].fi && d[i] == Min)
ans = (ans + c[i]) % MOD;
cout << ans;
return 0;
}