标签归档:splay

BZOJ 4864: [BeiJing 2017 Wc]神秘物质(splay)

Description

21ZZ 年,冬。
小诚退休以后, 不知为何重新燃起了对物理学的兴趣。 他从研究所借了些实验仪器,整天研究各种微观粒子。这
一天, 小诚刚从研究所得到了一块奇异的陨石样本, 便迫不及待地开始观测。 在精密仪器的视野下,构成陨石
的每个原子都无比清晰。 小诚发现, 这些原子排成若干列, 每一列的结构具有高度相似性。于是,他决定对单
独一列原子进行测量和测试。被选中的这列共有 N 个顺序排列的原子。 最初, 第 i 个原子具有能量 Ei。 随着
时间推移和人为测试, 这列原子在观测上会产生两种变化:
merge x e 当前第 x 个原子和第 x+1 个原子合并,得到能量为 e 的新原子;
insert x e 在当前第 x 个原子和第 x+1 个原子之间插入一个能量为 e 的新原子。
对于一列原子,小诚关心的是相邻一段中能量最大和能量最小的两个原子的能量差值,
称为区间极差。 因此, 除了观测变化外,小诚还要经常统计这列原子的两类数据:
max x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最大值;
min x y 当前第 x 到第 y 个原子之间的任意子区间中区间极差的最小值。
其中, 子区间指的是长度至少是 2 的子区间。
小诚坚信这项研究可以获得诺贝尔物理学奖。为了让小诚早日了结心愿,你能否帮助他实现上述的观测和测量呢?
Input

第一行, 两个整数 N, M, 分别表示最初的原子数目和事件总数。
第二行, N 个整数 E1, E2, …, EN, 由空格隔开。依次表示每个原子的能量。
接下来 M 行, 每行为一个字符串和两个整数, 描述一次事件,格式见题目描述。
N<=100,000,M<=100,000 1 ≤ e, Ei ≤ 109。 设 N’ 为当前时刻原子数目。 对于 merge 类事件, 1 ≤ x ≤ N’-1; 对于 insert 类事件, 1 ≤ x ≤ N’; 对于 max 和 min 类事件, 1 ≤ x < y ≤ N’。 任何时刻,保证 N’ ≥ 2。 Output 输出若干行, 按顺序依次表示每次 max 和 min 类事件的测量结果。 Sample Input 4 3 5 8 10 2 max 1 3 min 1 3 max 2 4 Sample Output 5 2 8 一个细节很多的题目。。。调了半天。。 因为随着一个区间的长度增大,其最大值减最小值的差值也会越来越大。所以对于一个区间来说,其极差最大的子区间就是整个区间,其极差最小的区间必然是相邻的两个数。 splay维护区间最大值和最小值,以及相邻两个数的差值即可。在插入和删除的时候修改相邻的两个数的差值(注意这里一定要把两个数都旋转到当前节点的左右两侧)。

BZOJ 1014: [JSOI2008]火星人prefix(二分hash+splay)

Description

  火星人最近研究了一种操作:求一个字串两个后缀的公共前缀。比方说,有这样一个字符串:madamimadam,
我们将这个字符串的各个字符予以标号:序号: 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在,
火星人定义了一个函数LCQ(x, y),表示:该字符串中第x个字符开始的字串,与该字符串中第y个字符开始的字串
,两个字串的公共前缀的长度。比方说,LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程
中,火星人发现了这样的一个关联:如果把该字符串的所有后缀排好序,就可以很快地求出LCQ函数的值;同样,
如果求出了LCQ函数的值,也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速
算法,但不甘心认输的地球人又给火星人出了个难题:在求取LCQ函数的同时,还可以改变字符串本身。具体地说
,可以更改字符串中某一个字符的值,也可以在字符串中的某一个位置插入一个字符。地球人想考验一下,在如此
复杂的问题中,火星人是否还能够做到很快地求取LCQ函数的值。

Input

  第一行给出初始的字符串。第二行是一个非负整数M,表示操作的个数。接下来的M行,每行描述一个操作。操
作有3种,如下所示
1、询问。语法:Qxy,x,y均为正整数。功能:计算LCQ(x,y)限制:1<=x,y<=当前字符串长度。
2、修改。语法:Rxd,x是正整数,d是字符。功能:将字符串中第x个数修改为字符d。限制:x不超过当前字
符串长度。
3、插入:语法:Ixd,x是非负整数,d是字符。功能:在字符串第x个字符之后插入字符d,如果x=0,则在字
符串开头插入。限制:x不超过当前字符串长度

Output

  对于输入文件中每一个询问操作,你都应该输出对应的答案。一个答案一行。

Sample Input

madamimadam
7
Q 1 7
Q 4 8
Q 10 11
R 3 a
Q 1 7
I 10 a
Q 2 11

Sample Output

5
1
0
2
1

HINT

1、所有字符串自始至终都只有小写字母构成。

2、M<=150,000

3、字符串长度L自始至终都满足L<=100,000

4、询问操作的个数不超过10,000个。

对于第1,2个数据,字符串长度自始至终都不超过1,000

对于第3,4,5个数据,没有插入操作。

发现是大白书上的某个题的弱化版,通过splay来维护字符串的hash值,询问可以二分判断LCP的长度。

但是hash的函数得弄的好一点,一不小心就T掉了。。。

 

BZOJ 1861: [Zjoi2006]Book 书架(splay)

Description

小T有一个很大的书柜。这个书柜的构造有些独特,即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 小T在看书的时候,每次取出一本书,看完后放回书柜然后再拿下一本。由于这些书太有吸引力了,所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的,所以每次放书的时候至少能够将那本书放在拿出来时的位置附近,比如说她拿的时候这本书上面有X本书,那么放回去时这本书上面就只可能有X-1、X或X+1本书。 当然也有特殊情况,比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面,然后转身离开。 久而久之,小T的书柜里的书的顺序就会越来越乱,找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序,处理她看书时的一些操作,以及回答她的两个提问:(1)编号为X的书在书柜的什么位置;(2)从上到下第i本书的编号是多少。

Input

第一行有两个数n,m,分别表示书的个数以及命令的条数;第二行为n个正整数:第i个数表示初始时从上至下第i个位置放置的书的编号;第三行到m+2行,每行一条命令。命令有5种形式: 1. Top S——表示把编号为S的书房在最上面。 2. Bottom S——表示把编号为S的书房在最下面。 3. Insert S T——T∈{-1,0,1},若编号为S的书上面有X本书,则这条命令表示把这本书放回去后它的上面有X+T本书; 4. Ask S——询问编号为S的书的上面目前有多少本书。 5. Query S——询问从上面数起的第S本书的编号。

Output

对于每一条Ask或Query语句你应该输出一行,一个数,代表询问的答案。

Sample Input

10 10
1 3 2 7 5 8 10 4 9 6
Query 3
Top 5
Ask 6
Bottom 3
Ask 3
Top 6
Insert 4 -1
Query 5
Query 2
Ask 2

Sample Output

2
9
9
7
5
3

HINT

数据范围

100%的数据,n,m < = 80000
打了个splay水水,开一个id数组,存每个值现在对应节点标号。然后最多不超过160000个节点,所以就不用回收内存哈哈哈。。。每次插入的时候先把对应的节点删除,再重新插入即可。