线段树
按照高度排序以后，对价格的值域建线段树，维护数量和总费用。
每次枚举一个高度，假设该高度的树有m棵，比它的高的树显然要全部砍掉，直接用前缀和统计费用，又假设比他低的树有n棵，
我们要砍的数量就是n - m + 1，在值域线段树里查询前n-m+1棵树的总费用即可。
#include#define INF 2333333333333333333#define full(a, b) memset(a, b, sizeof a)#define __fastIn ios::sync_with_stdio(false), cin.tie(0)#define range(x) (x).begin(), (x).end()#define pb push_backusing namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){ int ret = 0, w = 0; char ch = 0; while(!isdigit(ch)){ w |= ch == '-', ch = getchar(); } while(isdigit(ch)){ ret = (ret << 3) + (ret << 1) + (ch ^ 48); ch = getchar(); } return w ? -ret : ret;}template inline A lcm(A a, A b){ return a / __gcd(a, b) * b; }template inline A fpow(A x, B p, C lyd){ A ans = 1; for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd; return ans;}const int N = 200005;int n, cnt;LL sum[N<<2], pre[N], num[N], tree[N<<2], b[N];struct Tree{ int h, c, p; Tree(){} Tree(int h, int c, int p): h(h), c(c), p(p){} bool operator < (const Tree &rhs) const { return h < rhs.h; }}t[N];void init(){ cnt = 0; full(b, 0), full(pre, 0), full(num, 0); full(tree, 0), full(sum, 0);}void buildTree(int rt, int l, int r){ if(l == r){ tree[rt] = sum[rt] = 0; return; } int mid = (l + r) >> 1; buildTree(rt << 1, l, mid); buildTree(rt << 1 | 1, mid + 1, r);}void insert(int rt, int l, int r, int val, int k){ tree[rt] += 1LL * k, sum[rt] += 1LL * val * k; if(l == r) return; int mid = (l + r) >> 1; if(val <= mid) insert(rt << 1, l, mid, val, k); else insert(rt << 1 | 1, mid + 1, r, val, k);}LL query(int rt, int l, int r, LL k){ if(l == r) return l * k; int mid = (l + r) >> 1; if(k <= tree[rt << 1]) return query(rt << 1, l, mid, k); return sum[rt << 1] + query(rt << 1 | 1, mid + 1, r, k - tree[rt << 1]);}int main(){ while(~scanf("%d", &n)){ init(); for(int i = 1; i <= n; i ++){ scanf("%d%d%d", &t[i].h, &t[i].c, &t[i].p); } sort(t + 1, t + n + 1); int j; for(int i = 1; i <= n; i = j){ cnt ++, j = i; pre[cnt] += pre[cnt - 1], num[cnt] += num[cnt - 1]; while(j <= n && t[j].h == t[i].h){ pre[cnt] += 1LL * t[j].c * t[j].p; num[cnt] += t[j].p; b[cnt] += t[j].p; j ++; } } LL ans = INF; int tot = 0; for(int i = 1; i <= n; i = j){ tot ++, j = i; LL cur = pre[cnt] - pre[tot]; LL x = num[tot - 1]; if(x - b[tot] + 1 > 0) cur += query(1, 1, 200, x - b[tot] + 1); ans = min(ans, cur); while(j <= n && t[j].h == t[i].h) insert(1, 1, 200, t[j].c, t[j].p), j ++; } printf("%lld\n", ans); } return 0;}