icontofig | 发布于 2017-04-06 00:00:14 | 阅读量 159 | splay 线段树 树套树
发布于 2017-04-06 00:00:14 | splay 线段树 树套树
引言好久没写题解了,正好不怎么想写代码,还是来发波题解吧。 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,
继续阅读
icontofig | 发布于 2017-03-05 11:30:55 | 阅读量 123 | splay
发布于 2017-03-05 11:30:55 | splay
NOI2005 维修数列
 [NOI2005]维修数列Time Limit: 10 Sec  Memory Limit: 64 MBSubmit: 13351  Solved: 4272[Submit][Status][Discuss] Description Input输入的第1 行包含两个数N 和M(M ≤20 000),N 表示初始时数列中数的个数,M表示要进行的操作数目。第2行包含N个数字,描述初始时的数列。以下M行,每行一条命令,格式参见问题描述中的表格。任何时刻数列中最多含有500 000个数,数列中任何一个数字均在[
继续阅读
icontofig | 发布于 2017-01-08 09:23:48 | 阅读量 359 | splay 线段树
发布于 2017-01-08 09:23:48 | splay 线段树
【ZJOI2007】【BZOJ1058】报表统计splay+线段树
题目描述小Q的妈妈是一个出纳,经常需要做一些统计报表的工作。今天是妈妈的生日,小Q希望可以帮妈妈分担一些工作,作为她的生日礼物之一。经过仔细观察,小Q发现统计一张报表实际上是维护一个可能为负数的整数数列,并且进行一些查询操作。在最开始的时候,有一个长度为N的整数序列,并且有以下三种操作: INSERT i k 在原数列的第i个元素后面添加一个新元素k; 如果原数列的第i个元素已经添加了若干元素,则添加在这些元素的最后(见下面的例子) MIN_GAP 查询相邻两个元素的之间差值(绝对值)的最小值 MIN_SORT_GAP 查询所有元素中最接近的两个元素的差值(绝对值) 例如一开始的序列为 5 3
继续阅读
icontofig | 发布于 2017-01-06 17:56:04 | 阅读量 339 | splay
发布于 2017-01-06 17:56:04 | splay
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> using namespace std; const int maxn = 1e6+5; const int INF = 214748364
继续阅读