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+树状数组求随时间增长的区间和问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/881188

相关文章

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring

解决Maven项目idea找不到本地仓库jar包问题以及使用mvn install:install-file

《解决Maven项目idea找不到本地仓库jar包问题以及使用mvninstall:install-file》:本文主要介绍解决Maven项目idea找不到本地仓库jar包问题以及使用mvnin... 目录Maven项目idea找不到本地仓库jar包以及使用mvn install:install-file基

Java中字符串转时间与时间转字符串的操作详解

《Java中字符串转时间与时间转字符串的操作详解》Java的java.time包提供了强大的日期和时间处理功能,通过DateTimeFormatter可以轻松地在日期时间对象和字符串之间进行转换,下面... 目录一、字符串转时间(一)使用预定义格式(二)自定义格式二、时间转字符串(一)使用预定义格式(二)自

usb接口驱动异常问题常用解决方案

《usb接口驱动异常问题常用解决方案》当遇到USB接口驱动异常时,可以通过多种方法来解决,其中主要就包括重装USB控制器、禁用USB选择性暂停设置、更新或安装新的主板驱动等... usb接口驱动异常怎么办,USB接口驱动异常是常见问题,通常由驱动损坏、系统更新冲突、硬件故障或电源管理设置导致。以下是常用解决

Mysql如何解决死锁问题

《Mysql如何解决死锁问题》:本文主要介绍Mysql如何解决死锁问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录【一】mysql中锁分类和加锁情况【1】按锁的粒度分类全局锁表级锁行级锁【2】按锁的模式分类【二】加锁方式的影响因素【三】Mysql的死锁情况【1

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代