Tag-splay

Icontofig 's Blog // 我们的征程是星辰大海!Away From OI,Come to ICPC(查看友链请点About Me)

 2020-09-19 14:42:30 |  0 Comments  |  splay STL

Nowcoder Muti-School Training 2 H Happy Triangle multiset + splay平衡树

题目大意

维护一个多重集合,支持三种操作:

  • 1 : 加入一个x
  • 2 : 删除一个x
  • 3 : 询问当前在多重集中,是否存在两个数a,b,使得x能与a,b组成一个合法的三角形

题解

这题有线段树动态建点和离线离散化建线段树的做法,但是平衡树的做法一定是最好想的。

考虑查询操作我们可以假设下面两种情况:

  1. x为唯一最大边,则要a,b都小于x,于是只需要找比x更小的两个前驱作为a,b,判断a+b>x是否成立即可。
  2. x不是唯一最大边,假设b≥a,于是我们需要b≥x && b - a < x,而b-a最小的条件一定是b确定的情况下,a是b的一个非严格前驱,这样我们只需要找x的后缀最小值就行了。

第一种情况非常简单,直接用multiset维护、查询就行了,只需要注意一下边界问题。

第二种情况比较麻烦,没法用STL做,所以就用平衡树维护。平衡树维护的信息为子树内相邻两数差的最小值,排序的键值为当前数的大小,查询答案的时候,找到x的后缀节点,然后判断此节点与前一个节点的差mnval和其右子树中的相邻两数差的最小值mn中的最小值是否<x即可。

需要注意考虑边界问题。

最后提示的一点,s.lower_bound(x)和s.upper_bound(x)是比lower_bound(s.begin(),s.end(),x)和upper_bound(s.beign(),s.end(),x)要快不少的。我就被坑了……。

代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 2e9;
multiset<int>s;
const int maxn = 2e5+5;
typedef pair<int,int> PI;
struct splay_node{
    int siz;
    PI val;
    int mn;
    splay_node *fa,*ch[2];
    void update(){
        mn = min(val.second,min(ch[0]->mn,ch[1]->mn));
    }
    void set_ch(int type,splay_node *child);
    int get_wh(){
        return (this == this->fa->ch[0]) ? 0 : 1;
 2017-04-06 00:00:14 |  0 Comments  |  splay 线段树 树套树

BZOJ 3196 二逼平衡树

引言

好久没写题解了,正好不怎么想写代码,还是来发波题解吧。

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x,且最大的数)
5.查询k在区间内的后继(后继定义为大于x,且最小的数)

Input

第一行两个数 n,m 表示长度为n的有序序列和m个操作 第二行有n个数,表示有序序列
下面有m行,opt表示操作标号
若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继

Output

对于操作1,2,4,5各输出一行,表示查询结果

Sample Input

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围:n,m<=50000
2.序列中每个数的数据范围:[0,1e8]
3.虽然原题没有,但事实上5操作的k可能为负数

题解

这是一道线段树套平衡树(就是每个线段树节点里面都存着一颗平衡树)的裸题。。。
用线段树维护下标区间,然后把平衡树节点套到线段树节点里面,注意此处的平衡树节点维护的是权值的大小。 修改操作可以转化成为找到当前这个数对应的区间,在splay里面删掉这个数,然后插入修改成的那个数就OK。
然后就是注意排名的话是比当前小的数的个数+1。
要求区间内排名为k的数的时候,我们就得注意了。因为我们是线段树套平衡树,所以说查询区间的时候,查询区间会分布在很多个线段树节点上。所以这样的话,这个操作就只能是二分答案,然后去看答案的排名是不是在这个查询区间中排k。(注意因为有重复的数,所以要求最大排名和最小排名,看k是不是在这个范围内)。
最后要注意的就是……为了保证空间,一律用内存池写。(可能我的代码里面的指针对某些读者不太友善。。。)

代码

#includ
 2017-03-05 11:30:55 |  1 Comments  |  splay

NOI2005 维修数列

 [NOI2005]维修数列

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 13351  Solved: 4272
[Submit][Status][Discuss]

Description

Input

输入的第1 行包含两个数N 和M(M ≤20 000),N 表示初始时数列中数的个数,M表示要进行的操作数目。
第2行包含N个数字,描述初始时的数列。
以下M行,每行一条命令,格式参见问题描述中的表格。
任何时刻数列中最多含有500 000个数,数列中任何一个数字均在[-1 000, 1 000]内。
插入的数字总数不超过4 000 000个,输入文件大小不超过20MBytes。

Output

对于输入数据中的GET-SUM和MAX-SUM操作,向输出文件依次打印结果,每个答案(数字)占一行。

Sample Input

9 8 2 -6 3 5 1 -5 -3 6 3 
GET-SUM 5 4
MAX-SUM
INSERT 8 3 -5 7 2
DELETE 12 1
MAKE-SAME 3 3 2
REVERSE 3 6
GET-SUM 5 4
MAX-SUM
​

Sample Output

-1
10
1
10
​

HINT


 

Solution(题解)

splay操作集大成者,如果这道题能懂的话,基本就不用愁splay的题了吧……

不想说什么,做到心态爆炸才调出来……

好,那既然是基本操作题,那我们就来基本操作吧。。。

首先不得不说平衡树的性质,那就是关键字大的节点一定在关键字小的节点的右边→_→;反之同理。

然后来说区间操作。假设我们要对区间[L,R]进行操作,那么我们就把节点L-1 rotate到根,把节点R+1 rotate到L-1的右儿子,那么根的右儿子的左子树就是区间[L,R]。为什么呢?因为根的右儿子的左子树的所有节点都在L-1右边、R+1左边,所以满足根的有儿子的左子树的所有节点的关键字x都满足L-1 < x < R+1,自然就是所要的区间了。(当然这是针对序列而言,关键字为第几个数的情况下)

然后来说这道题的6个操作

首先来说MAKE-SAME和REVERSE操作,这两个操作就是更新找出所求区间对应的子树后的根节点,然后再打上lazy标记,然后随着rotate和find操作push_down下传标记就好。

但是因为要维护最大子段和(MAX-SE

 2017-01-08 09:23:48 |  0 Comments  |  splay 线段树

【ZJOI2007】【BZOJ1058】报表统计splay+线段树

题目描述

小Q的妈妈是一个出纳,经常需要做一些统计报表的工作。今天是妈妈的生日,小Q希望可以帮妈妈分担一些工作,作为她的生日礼物之一。经过仔细观察,小Q发现统计一张报表实际上是维护一个可能为负数的整数数列,并且进行一些查询操作。在最开始的时候,有一个长度为N的整数序列,并且有以下三种操作: INSERT i k 在原数列的第i个元素后面添加一个新元素k; 如果原数列的第i个元素已经添加了若干元素,则添加在这些元素的最后(见下面的例子) MIN_GAP 查询相邻两个元素的之间差值(绝对值)的最小值 MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值(绝对值) 例如一开始的序列为 5 3 1 执行操作INSERT 2 9将得到: 5 3 9 1 此时MIN_GAP为2,MIN_SORT_GAP为2。 再执行操作INSERT 2 6将得到: 5 3 9 6 1 注意这个时候原序列的第2个元素后面已经添加了一个9,此时添加的6应加在9的后面。这个时候MIN_GAP为2,MIN_SORT_GAP为1。于是小Q写了一个程序,使得程序可以自动完成这些操作,但是他发现对于一些大的报表他的程序运行得很慢,你能帮助他改进程序么?

输入格式

第一行包含两个整数N,M,分别表示原数列的长度以及操作的次数。第二行为N个整数,为初始序列。接下来的M行每行一个操作,即“INSERT i k”,“MIN_GAP”,“MIN_SORT_GAP”中的一种(无多余空格或者空行)。

输出格式

对于每一个“MIN_GAP”和“MIN_SORT_GAP”命令,输出一行答案即可。

样例输入

3 5
5 3 1
INSERT 2 9
MIN_SORT_GAP
INSERT 2 6
MIN_GAP
MIN_SORT_GAP

样例输出

2
2
1

数据范围及提示

N , M ≤500000 对于所有的数据,序列内的整数不超过5*108


题解

于是这道题有点坑啊。
初学splay,拿几道题目练练手,结果没想到刚开始推荐的这个就这么坑。
观察题目中的信息,我们发现,其实是可以用2个splay做的,一个splay维护MIN_GAP,另一个维护MIN_SORT_GAP,每次添加的时候只要注意:
1.由于满足单调性MIN_SORT_GAP只需要先求出排在当前要添加的数的前面和后面的两个数,用这两个数和当前要添加的数的差值的绝对值更新MIN_SORT_GAP,然后

 2017-01-06 17:56:04 |  0 Comments  |  splay

splay核心代码(指针)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int maxn = 1e6+5;
const int INF = 2147483647;
struct splay_node{
    int value,siz,cnt;
    splay_node *pre,ch[2];
    void update(){
        siz = ch[0]->siz + ch[1]->siz + cnt;
    }
    int get_wh(){
        return pre->ch[0] == this ? 0 : 1;
    }
    void set_ch(int wh,splay_node *now);
}pool[maxn],*root,*null;
int top = 0;
splay_node get_new(int value){
    splay_node *now = pool + ++top;
    now->value = value;
    now->cnt = now->siz = 1;
    now->pre = now->ch[1] = now->ch[0] = null;
    return now;
}
inline splay_node::void set_ch(int wh,spaly_node *now){
    this->ch[wh] = now;
    if(now != null)now->pre = this;
    this->update();
    return;
}
inline void rotate(splay_node *&now){
    spaly_node *oldf = now->pre,*grand = now->pre->pre;
    int wh = now->get_wh();
    oldf->set_ch(wh,now->ch[wh^1]);
    now->set_ch(wh^1,oldf);
    now
Title - Artist
0:00