分类 平衡树 下的文章

BZOJ 1251: 序列终结者

SolutionSplay 基础题...Code#include <cstdio> #include <algorithm> #include <iostream> #define long long long using namespace std; long n, m; const long N = 50010; struct Node { long max, val, tag, size; bool rev; Node *ch[2], *fa; }pool[N], *null, *root; Node *ne- 阅读剩余部分 -

BZOJ 1014: [JSOI2008]火星人prefix

Solution用 Splay 维护区间 hash 值,然后每次二分长度即可。需要注意的就是这道题的哈希方式,如果想要支持合并操作,需要这么哈希:cur->hash = ls->hash + convert(cur->val) * base[ls->size] + base[ls->size+1] * rs->hash;可以发现每次是左儿子的哈希值 + 自身的值乘左儿子的大小 + 右儿子的哈希值乘上(左儿子大小+1)。这么做我们可以发现,每个数最终都会乘上比自己编号小的点数 - 1。所以树的结构不影响哈希值,就可以放心的用 splay 维- 阅读剩余部分 -

BZOJ 1500: [NOI2005]维修数列

Solution这个题可以说是十分恶心了,但是并没有考太多思维方面的东西,主要考验代码能力,这道题任何一个操作单拿出来做都是比较基础的,混合到一起就比较难以调试了,需要我们理清楚代码的所有细节,我就列出一些需要注意的地方吧!需要插入两个占位的点,分别当做数列头和数列尾,他们的值应该设成 -INF 而不是零或其他值,否则求最大子序列的时候会出错,比如全是负数的数列,如果占位点的值设成零,那么最大子序列的值求出来是零,显然是错误的。注意好空节点,对于指针版是指 null 节点,对于数组版一般值 0 号节点,这些节点的值必须为 0,他们以自身为根的子树大小应该是 0,最重要的是他- 阅读剩余部分 -

BZOJ 1208: [HNOI2004]宠物收养所

Description最近,阿Q开了一间宠物收养所。收养所提供两种服务:收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物,阿Q根据领养者的要求通过他自己发明的一个特殊的公式,得出该领养者希望领养的宠物的特点值a(a是一个正整数,a<2^31),而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了,宠物收养所总是会有两种情况发生:被遗弃的宠物过多或者是想要收养宠物的人太多,而宠物太少。 1. 被遗弃的宠物过多时,假若到来一个领养者,这个领养者希望领养的宠物的特点值为a,那么它将会领养一只目前未被领养的宠物- 阅读剩余部分 -

BZOJ 3223: Tyvj 1729 文艺平衡树

Description您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1Input第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2……n-1,n) m表示翻转操作次数接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=nOutput输出一行n个数字,表示原始序列经过m次变换后的结果Sample Input5 3 1 3 1 3 1 4Sample Output4 3 2 1 5HINTN,M<=1- 阅读剩余部分 -

BZOJ 1503: [NOI2004]郁闷的出纳员

DescriptionOIER公司是一家大型专业化软件公司,有着数以万计的员工。作为一名出纳员,我的任务之一便是统计每位员工的工资。这本来是一份不错的工作,但是令人郁闷的是,我们的老板反复无常,经常调整员工的工资。如果他心情好,就可能把每位员工的工资加上一个相同的量。反之,如果心情不好,就可能把他们的工资扣除一个相同的量。我真不知道除了调工资他还做什么其它事情。工资的频繁调整很让员工反感,尤其是集体扣除工资的时候,一旦某位员工发现自己的工资已经低于了合同规定的工资下界,他就会立刻气愤地离开公司,并且再也不会回来了。每位员工的工资下界都是统一规定的。每当一个人离开公司,我就要- 阅读剩余部分 -

【模板】Splay 模板

Splay 模板自己写的模板。#include <cstdio> const int N = 200000; struct node {int d, n, c, f, son[2];}tr[N]; int cnt, root; void up(int x) { int lc = tr[x].son[0], rc = tr[x].son[1]; tr[x].c = tr[lc].c + tr[rc].c + tr[x].n; } int type(int son) {return tr[tr[son].f].son[1] == son;} void- 阅读剩余部分 -

BZOJ 1588: [HNOI2002]营业额统计

题目描述营业额统计 Tiger最近被公司升任为营业部经理,他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。 Tiger拿出了公司的账本,账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日,大减价或者是其他情况的时候,营业额会出现一定的波动,当然一定的波动是能够接受的,但是在某些时候营业额突变得很高或是很低,这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况: 该天的最小波动值 当最小波动值越大时,就说明营业情况越不稳定。 而分析整个公司的从成立到现在营业情况是否稳定,只需要把每一天的最小- 阅读剩余部分 -