题解 | #购物#
购物
https://www.nowcoder.com/practice/ca7f5b2c0c91465f9ce0f15973e2e976
/* * 不是特别懂,这个思路,照着题解敲一遍,日后再来,好好研究!!! */ #include <bits/stdc++.h> using namespace std; typedef long long ll; const ll maxn = 1000000; vector<ll> seg(maxn), seg2(maxn); // 两个线段树! void pushup(int node) { if (seg[node << 1] <= seg[node << 1 | 1]) { seg[node] = seg[node << 1]; seg2[node] = seg2[node << 1]; } else { seg[node] = seg[node << 1 | 1]; seg2[node] = seg2[node << 1 | 1]; } } void build(int l, int r, int node) { if (l == r) { seg[node] = 0; seg2[node] = l; return ; } int mid = (l + r) >> 1; build(l, mid, node << 1); // 左孩子 build(mid + 1, r, node << 1 | 1); // 右孩子! pushup(node); } pair<ll, ll> nums[maxn]; ll ret(0); void update(int l, int r, int pos, int node, ll ai, ll c) { if (l == r) { seg[node] = max(seg[node], ai) + c; ret = max(ret, seg[node]); return ; } int mid = (l + r) >> 1; if (pos <= mid) { update(l, mid, pos, node << 1, ai, c); } else { update(mid + 1, r, pos, node << 1 | 1, ai, c); } pushup(node); } int main() { int n, m; cin >> n >> m; build(1, m, 1); vector<ll> a(n + 1), s(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i] >> s[i]; nums[i] = make_pair(a[i], s[i]); } sort(nums + 1, nums + n + 1); for (int i = 1; i <= n; i++) { int pos = seg2[1]; update(1, m, pos, 1, nums[i].first, nums[i].second); } cout << ret << endl; return 0; }