2019牛客暑期多校训练营（第七场）F Energy stones —— set+树状数组求随时间增长的区间和问题

本文主要是介绍2019牛客暑期多校训练营（第七场）F Energy stones —— set+树状数组求随时间增长的区间和问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

This way

题意：

有n个石头，这些石头一开始有一些能量e[i]，并且每过一个单位的时间会增长l[i]，直到有c[i]的能量为止。现在有q个询问
t l r表示在t时刻的时候收割l-r的所有能量，并且将其能量置为0，然后这些石头的能量重新增长。问你最后你收割了多少能量

题解：

for一遍所有的石头，用一个set维护在这个时候有哪些收割的时刻。
每个石头有两种状态：未达到c[i]和已达到c[i]
entir树状数组维护达到c[i]的数量
half树状数组维护未达到c[i]的时间的总和
还需要特判一下第一次收割的情况。
新进来一个时间的时候，它的位置总共可分为三种情况：
1.在最下面

红色的表示新进来的时间，那么这个时候树状数组就可以加入红色到最下面黑色的值，因为我们是特判第一个位置的来着。

第二种情况是在中间

那么就是减掉第三个区间，加上第一个和第二个区间
第三种情况就是在最上面

这样就只需要在树状数组中加入值即可

代码贼丑，理解了其中的道理之后自己去敲吧

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=1e5+5;
struct Add
{int l;ll y;bool operator< (const Add& a)const{return l<a.l;}
}add[N];
struct Del
{int r;ll y;bool operator< (const Del& a)const{return r<a.r;}
}del[N];
ll e[N],l[N],c[N],half[N*2],entir[N*2];
set<ll>now;
int lowbit(int x){return x&(-x);}
void add_e(int x,int v)
{for(int i=x;i;i-=lowbit(i))entir[i]+=v;
}
ll q_e(int x)
{ll ans=0;for(int i=x;i<N*2;i+=lowbit(i))ans+=entir[i];return ans;
}
void add_h(int x,ll f)
{for(int i=x;i<N*2;i+=lowbit(i))half[i]+=(ll)x*f;
}
ll q_h(int x)
{ll ans=0;for(int i=x;i;i-=lowbit(i))ans+=half[i];return ans;
}
int main()
{int t,cas=0;scanf("%d",&t);while(t--){now.clear();memset(entir,0,sizeof(entir));memset(half,0,sizeof(half));int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%lld%lld%lld",&e[i],&l[i],&c[i]);int q;scanf("%d",&q);for(int i=1;i<=q;i++){int t,x,y;scanf("%d%d%d",&t,&x,&y);add[i].l=x,add[i].y=t;del[i].r=y+1,del[i].y=t;}sort(add+1,add+1+q),sort(del+1,del+1+q);int padd=1,pdel=1;ll ans=0;set<ll>::iterator it,sit;for(int i=1;i<=n;i++){//delwhile(del[pdel].r==i){// printf("%lld\n",j);it=now.find(del[pdel].y);if(it==now.end())continue;sit=it;sit++;if(it==now.begin()){if(sit!=now.end()){int tim=*sit-*it;add_e(tim,-1);add_h(tim,-1);}}else if(sit==now.end()){sit=it;sit--;int tim=*it-*sit;add_e(tim,-1);add_h(tim,-1);}else{int tim=*sit-*it;add_e(tim,-1);add_h(tim,-1);sit--;it--;tim=*sit-*it;add_e(tim,-1);add_h(tim,-1);sit++;tim=*sit-*it;add_e(tim,1);add_h(tim,1);}now.erase(now.find(del[pdel].y));pdel++;}//addwhile(add[padd].l==i){it=now.find(add[padd].y);if(it!=now.end())continue;now.insert(add[padd].y);it=now.find(add[padd].y);sit=it;sit++;if(it==now.begin()){if(sit!=now.end()){int tim=*sit-*it;add_e(tim,1);add_h(tim,1);}}else if(sit==now.end()){sit=it;sit--;int tim=*it-*sit;add_e(tim,1);add_h(tim,1);}else{int tim=*sit-*it;add_e(tim,1);add_h(tim,1);sit--;it--;tim=*sit-*it;add_e(tim,1);add_h(tim,1);sit++;tim=*sit-*it;add_e(tim,-1);add_h(tim,-1);}padd++;}if(!now.empty()){ll sta=*now.begin();if(sta*l[i]+e[i]<=c[i])ans+=sta*l[i]+e[i];elseans+=c[i];if(l[i]!=0){ans+=c[i]*q_e((c[i]+l[i]-1)/l[i]);ans+=l[i]*q_h((c[i]-1)/l[i]);}}}printf("Case #%d: %lld\n",++cas,ans);}return 0;
}

这篇关于2019牛客暑期多校训练营（第七场）F Energy stones —— set+树状数组求随时间增长的区间和问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---