HYSBZ 1588 营业额统计 伸展树

2024-01-19 03:58

本文主要是介绍HYSBZ 1588 营业额统计 伸展树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1588
题意:每次查找集合中一个key对于给定的tmp满足 |tmp-key|最小,将tmp加入集合
维护每次的最小差值
第一道伸展树题,大神的模板很好用

代码:

#include <bits/stdc++.h>
#define sf scanf
#define pf printf
using namespace std;
const int maxn = 100000 + 50;
typedef long long LL;
const LL INF = 10000000000;
int sroot,root,tot,ch[maxn][2],fa[maxn];
LL key[maxn];/**
**  NewNode
*/
void NewNode(int& rt,int FA,LL k){rt = tot++;fa[rt] = FA;key[rt] = k;ch[rt][0] = ch[rt][1] = 0;
}
/**  kind 0 for zig
**   kind 1 for zag
*/
void rotate(int rt,int kind){int prt = fa[rt];ch[prt][kind] = ch[rt][!kind];fa[ch[rt][!kind]] = prt;if(fa[prt] != sroot){ch[ fa[ prt ] ][ (ch[ fa[ prt ] ][1] == prt) ] = rt;}fa[rt] = fa[prt];ch[rt][!kind] = prt;fa[prt] = rt;
}/** goal sroot for splay rt to root
**  kind 0 left son to zig operation
**  kind 1 right son to zag operation
*/
void Splay(int rt,int goal){while(fa[rt] != goal){//父节点就是目标节点 直接进行一次旋转if(fa[fa[rt]] == goal)rotate(rt,ch[fa[rt]][1] == rt);else{int prt = fa[rt];int kind = (ch[fa[prt]][1] == prt);if(ch[prt][kind] == rt){    //一字型rotate(rt,kind);}else{                       //之字型rotate(rt,!kind);rotate(rt,kind);}}}if(goal == sroot) root = rt;
}int Insert(LL k){int rt = root;while(ch[rt][key[rt] < k]){if(key[rt] == k){Splay(rt,sroot);return 0;}rt = ch[rt][key[rt] < k];}NewNode(ch[rt][key[rt] < k],rt,k);Splay(ch[rt][key[rt] < k],sroot);return 1;
}LL Find_Pre(){int rt = ch[root][0];if(rt == 0) return INF;while(ch[rt][1]) rt = ch[rt][1];return key[rt];
}
LL Find_Next(){int rt = ch[root][1];if(rt == 0) return INF;while(ch[rt][0]) rt = ch[rt][0];return key[rt];
}LL fabs(LL k){return  k > 0 ? k : -k;
}
int main(){int n;while( ~sf("%d",&n) ){sroot = root = 0,fa[0] = 0;ch[root][0] = ch[root][1] = 0;LL tmp,ans = 0;tot = 1;sf("%lld",&tmp);Insert(tmp);
//        pf("Start:\n");ans += tmp;for(int i = 1;i < n;++i){sf("%lld",&tmp);if(!Insert(tmp)) continue;else{ans += min(fabs(tmp - Find_Next()),fabs(tmp - Find_Pre()));}
//            pf("tmp = %lld key %lld\n",tmp,key[root]);}pf("%lld\n",ans);}return 0;
}

这篇关于HYSBZ 1588 营业额统计 伸展树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

hdu1496(用hash思想统计数目)

作为一个刚学hash的孩子,感觉这道题目很不错,灵活的运用的数组的下标。 解题步骤:如果用常规方法解,那么时间复杂度为O(n^4),肯定会超时,然后参考了网上的解题方法,将等式分成两个部分,a*x1^2+b*x2^2和c*x3^2+d*x4^2, 各自作为数组的下标,如果两部分相加为0,则满足等式; 代码如下: #include<iostream>#include<algorithm

flume系列之:查看flume系统日志、查看统计flume日志类型、查看flume日志

遍历指定目录下多个文件查找指定内容 服务器系统日志会记录flume相关日志 cat /var/log/messages |grep -i oom 查找系统日志中关于flume的指定日志 import osdef search_string_in_files(directory, search_string):count = 0

hdu4267区间统计

题意:给一些数,有两种操作,一种是在[a,b] 区间内,对(i - a)% k == 0 的加value,另一种操作是询问某个位置的值。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import

hdu4417区间统计

给你一个数列{An},然后有m次查询,每次查询一段区间 [l,r] <= h 的值的个数。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamRead

hdu3333区间统计

题目大意:求一个区间内不重复数字的和,例如1 1 1 3,区间[1,4]的和为4。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

实例:如何统计当前主机的连接状态和连接数

统计当前主机的连接状态和连接数 在 Linux 中,可使用 ss 命令来查看主机的网络连接状态。以下是统计当前主机连接状态和连接主机数量的具体操作。 1. 统计当前主机的连接状态 使用 ss 命令结合 grep、cut、sort 和 uniq 命令来统计当前主机的 TCP 连接状态。 ss -nta | grep -v '^State' | cut -d " " -f 1 | sort |

Python脚本:TXT文档行数统计

count = 0 #计数变量file_dirs = input('请输入您要统计的文件根路径:')filename = open(file_dirs,'r') #以只读方式打开文件file_contents = filename.read() #读取文档内容到file_contentsfor file_content in file_contents:

【Python 千题 —— 算法篇】字符统计

Python 千题持续更新中 …… 脑图地址 👉:⭐https://twilight-fanyi.gitee.io/mind-map/Python千题.html⭐ 题目背景 在编程中,对字符串的字符统计是一个常见任务。这在文本处理、数据分析、词频统计、自然语言处理等领域有广泛应用。无论是统计字母出现的频率,还是分析不同字符类型的数量,字符串字符统计都是非常有用的技术。 字符统

YOLOv8/v10+DeepSORT多目标车辆跟踪(车辆检测/跟踪/车辆计数/测速/禁停区域/绘制进出线/绘制禁停区域/车道车辆统计)

01:YOLOv8 + DeepSort 车辆跟踪 该项目利用YOLOv8作为目标检测模型,DeepSort用于多目标跟踪。YOLOv8负责从视频帧中检测出车辆的位置,而DeepSort则负责关联这些检测结果,从而实现车辆的持续跟踪。这种组合使得系统能够在视频流中准确地识别并跟随特定车辆。 02:YOLOv8 + DeepSort 车辆跟踪 + 任意绘制进出线 在此基础上增加了用户

一个统计文件中关键词数量的小程序-优化版本

public class computeWxxFileNum{public static void main(String[] args) throws IOException {//读文件File sourceFile = new File("e:\\55-tmp\\xxx.log");FileReader in = new FileReader(sourceFile); LineNumber