splay - hzwer.com

「BZOJ1208」[HNOI2004] 宠物收养所
Description最近，阿Q开了一间宠物收养所。收养所提供两种服务：收养被主人遗弃的宠物和让新的主人领养这些宠物。每个领养者都希望领养到自己满意的宠物，阿Q根据领养者的要求通过他自己发明的一个特殊的公式，得出该领养者希望领养的宠物的特点值a（a是一个正整数，a<2^31），而他也给每个处在收养所的宠物一个特点值。这样他就能够很方便的处理整个领养宠物的过程了，宠物收养所总是会有两种情况发生：被遗弃的宠物过多或者...
82016年6月14日19,139STL,splay

「BZOJ3729」Gty的游戏
Description某一天gty在与他的妹子玩游戏。妹子提出一个游戏，给定一棵有根树，每个节点有一些石子，每次可以将不多于L的石子移动到父节点，询问将某个节点的子树中的石子移动到这个节点先手是否有必胜策略。gty很快计算出了策略。但gty的妹子十分机智，她决定修改某个节点的石子或加入某个新节点。gty不忍心打击妹子，所以他将这个问题交给了你。另外由于gty十分绅士，所以他将先手让给了妹子。Input第一行两个数字，n和L,n&l...
122015年7月5日6,076STL,splay
「CODEVS1743」反转卡片
题目描述Description「dzy493941464|yywyzdzr原创」小A将N张卡片整齐地排成一排，其中每张卡片上写了1~N的一个整数，每张卡片上的数各不相同。比如下图是N=5的一种情况：34215接下来你需要按小A的要求反转卡片，使得左数第一张卡片上的数字是1。操作方法：令左数第一张卡片上的数是K，如果K=1则停止操作，否则将左数第1~K张卡片反转。第一次(K=3)反转后得到：24315第二次(K=2)反转后得到：42315第三次(K=4)反转后得到：...
22014年12月10日5,465splay
「BZOJ1552 / 3506」[Cerc2007] robotic sort
DescriptionInput输入共两行，第一行为一个整数N，N表示物品的个数，1<=N<=100000。第二行为N个用空格隔开的正整数，表示N个物品最初排列的编号。Output输出共一行，N个用空格隔开的正整数P1,P2,P3…Pn，（1<=Pi<=N），Pi表示第i次操作前第i小的物品所在的位置。注意：如果第i次操作前，第i小的物品己经在正确的位置Pi上，我们将区间[Pi,Pi]反转(单个物品)。SampleInput6345162SampleOutput464...
22014年9月10日6,047splay
「BZOJ1014」[JSOI2008] 火星人prefix
Description火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，我们将这个字符串的各个字符予以标号：序号：1234567891011字符madamimadam现在，火星人定义了一个函数LCQ(x,y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串，两个字串的公共前缀的长度。比方说，LCQ(1,7)=5,LCQ(2,10)=1,LCQ(4,7)=0在研究LCQ函数的过程中，火星人发现了...
42014年8月12日10,000splay,二分法,哈希表
「BZOJ1861」[ZJOI2006] Book 书架
Description小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本...
22014年8月1日5,729splay
NOI2005维修数列
DescriptionInput输入文件的第1行包含两个数N和M，N表示初始时数列中数的个数，M表示要进行的操作数目。第2行包含N个数字，描述初始时的数列。以下M行，每行一条命令，格式参见问题描述中的表格。Output对于输入数据中的GET-SUM和MAX-SUM操作，向输出文件依次打印结果，每个答案（数字）占一行。SampleInput982-6351-5-363GET-SUM54MAX-SUMINSERT83-572DELETE121MAKE-SAME...
252014年7月30日23,565splay
「BZOJ3223」JoyOI 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次变换后的结果SampleInput53131314...
262014年7月22日17,555splay
「BZOJ1251」序列终结者
Description网上有许多题，就是给定一个序列，要你支持几种操作：A、B、C、D。一看另一道题，又是一个序列要支持几种操作：D、C、B、A。尤其是我们这里的某人，出模拟试题，居然还出了一道这样的，真是没技术含量……这样我也出一道题，我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠，没有什么其他的意思。这道题目就叫序列终结者吧。「问题描述」给定一个长度为N的序列，每个序列的元素是一个整数（...
172014年7月21日8,435splay
「BZOJ1588」[HNOI2002] 营业额统计
Description营业额统计Tiger最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理...
32014年3月28日8,509treap,链表,splay
NOI2004郁闷的出纳员
输入描述 InputDescription第一行有两个非负整数n和min。n表示下面有多少条命令，min表示工资下界。接下来的n行，每行表示一条命令。命令可以是以下四种之一：名称格式作用I命令I_k新建一个工资档案，初始工资为k。如果某员工的初始工资低于工资下界，他将立刻离开公司。A命令A_k把每位员工的工资加上kS命令S_k把每位员工的工资扣除kF命令F_k查询第k多的工资_（下划线）表示一个空格，I命令、A命令、S命令中的k是一个...
82013年12月26日13,471treap,splay,线段树