牛客第七场 F Energy stones —— set + 树状数组

题目链接：点我啊╭(╯^╰)╮

题目大意：

    每颗石头初始能量是 $e[i]$, 每秒钟增加 $l[i]$, 上限是 $c[i]$
    区间收割 $M$ 次，求收割能量的总和
    收割时候会把区间里的能量都变为 $0$

解题思路：

    考虑枚举每个石头的贡献
    假设已经处理出每个石头的所有时间差后
    时间差 $\ge \frac{c[i]}{l[i]}$，每个贡献为 $c[i]$
    时间差 $＜\frac{c[i]}{l[i]}$，贡献为 $\sum t\times l[i]$
    那么维护两个树状数组，维护时间差的个数和时间总数

    那么怎么维护这个时间差呢？
    对于每一次收割 $（t_i，S_i，T_i）$
    那么就在 $S_i$ 插入 $t_i$ 这个时间点
    在 $T_i+1$ 删除这个时间点
    用 $set$ 维护时间点，插入就是一条时间线切成两条时间线
    删除就是两条时间线合并成一条

核心：set维护时间差

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
//#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long ll;
using pii = pair <ll,int>;
const int maxn = 2e5 + 5;
int T, cas, n, m;
ll e[maxn], c[maxn], l[maxn];
set <int> s;
vector <int> h[maxn];struct BIT{int N;ll c[maxn];inline int lowbit(int x){return x & (-x);}inline void init(int l){N = l;for(int i=0; i<=N; i++)c[i] = 0;}void add(int x, int v){for(; x<=N; x+=lowbit(x))c[x] += v;}ll sum(int x){ll ret = 0;for(; x; x-=lowbit(x))ret += c[x];return ret;}
} a, b;void add(int x){if(s.size() == 0) {s.insert(x);return;}auto p = s.lower_bound(x);if(p == s.begin()){int t = (*p) - x;a.add(t, 1);b.add(t, t);}else if(p == s.end()){int t = x - (*(prev(p)));a.add(t, 1);b.add(t, t);}else {int t1 = (*p) - x;int t2 = x - (*(prev(p)));a.add(t1, 1), a.add(t2, 1);b.add(t1, t1), b.add(t2, t2);a.add(t1 + t2, -1);b.add(t1 + t2, -t1 - t2);}s.insert(x);
}void del(int x){auto p = s.find(x);if(s.size() == 1) {s.erase(p);return;}if(p == s.begin()){int t = (*(next(p))) - x;a.add(t, -1), b.add(t, -t);}else if(p == prev(s.end())){int t = x - (*(prev(p)));a.add(t, -1), b.add(t, -t);}else {int t1 = (*(next(p))) - x;int t2 = x - (*(prev(p)));a.add(t1, -1), a.add(t2, -1);b.add(t1, -t1), b.add(t2, -t2);a.add(t1 + t2, 1);b.add(t1 + t2, t1 + t2);}s.erase(p);
}int main() {scanf("%d", &T);while(T--){s.clear();scanf("%d", &n);a.init(maxn), b.init(maxn);for(int i=1; i<=n+1; i++) h[i].clear();for(int i=1; i<=n; i++)scanf("%lld%lld%lld", e+i, l+i, c+i);scanf("%d", &m);while(m--){int t, l, r;scanf("%d%d%d", &t, &l, &r);h[l].push_back(t);h[r+1].push_back(-t);}ll ans = 0;for(int i=1; i<=n+1; i++){for(auto j : h[i]){if(j > 0) add(j);else del(-j);}if(s.size() == 0) continue;ans += min(c[i], e[i] + (*s.begin()) * l[i]);if(!l[i]) continue;ll d = c[i] / l[i];ans += b.sum(d) * l[i] + (s.size()-1-a.sum(d)) * c[i];}printf("Case #%d: %lld\n", ++cas, ans);}
}