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

相关文章

springboot循环依赖问题案例代码及解决办法

《springboot循环依赖问题案例代码及解决办法》在SpringBoot中,如果两个或多个Bean之间存在循环依赖(即BeanA依赖BeanB,而BeanB又依赖BeanA),会导致Spring的... 目录1. 什么是循环依赖?2. 循环依赖的场景案例3. 解决循环依赖的常见方法方法 1:使用 @La

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

MySQL新增字段后Java实体未更新的潜在问题与解决方案

《MySQL新增字段后Java实体未更新的潜在问题与解决方案》在Java+MySQL的开发中,我们通常使用ORM框架来映射数据库表与Java对象,但有时候,数据库表结构变更(如新增字段)后,开发人员可... 目录引言1. 问题背景:数据库与 Java 实体不同步1.1 常见场景1.2 示例代码2. 不同操作

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

Nginx指令add_header和proxy_set_header的区别及说明

《Nginx指令add_header和proxy_set_header的区别及说明》:本文主要介绍Nginx指令add_header和proxy_set_header的区别及说明,具有很好的参考价... 目录Nginx指令add_header和proxy_set_header区别如何理解反向代理?proxy

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.