题目背景

SkyDec和YJQQQAQ都是Yazid的好朋友。他们都非常喜欢吃火锅。有一天,他们聚在一起,享受一场火锅盛宴。

题目描述

在这场火锅盛宴中,有一个麻辣浓汤锅底的火锅和n种食物,每种食物数量都是无限的。我们用

11

nn

将这些食材编号。

每种食物煮熟所需要的时间不同,第

ii

种食物煮熟需要

sis_i

单位时间。这表示如果你在第

TT

个时刻将一个食物

ii

下到火锅里,那么它会在第

T+siT+s_i

个时刻被煮熟,并且此后一直会延续被煮熟的状态,直到它被拿走为止。

Yazid和YJQQQAQ的口味不同:YJQQQAQ觉得所有食物的好吃程度都是相同的;而Yazid则觉得没有两种食材的好吃程度是相同的,并且,巧合的是,编号越小的食物Yazid越喜欢吃。可怜的SkyDec由于不能吃辣,所以只能帮Yazid和YJQQQAQ煮食物。

整个火锅盛宴持续

10910^9

单位时间。在整个盛宴中,三位好朋友除了谈笑风生之外,最重要的事当然就是吃东西了。在任意整数时刻,都有可能发生下列4种事件中的任意一种,我们用

00

33

之间的整数

opop

描述事件类型:

0 id:表示SkyDec往火锅里下了一个编号为

idid

的食物。

1:Yazid在锅内搜寻熟了的且最喜欢吃的食物,并拿走一个这种食物。特别地,如果锅里没有熟了的食物,那么Yazid会很愤怒。

2 id:YJQQQAQ在锅内搜寻编号为

idid

的食物:如果锅里不存在该种食物,则YJQQQAQ会很愤怒;如果锅里存在熟了的该食物,则YJQQQAQ会取走一个并食用;如果锅里只有未煮熟的该种食物,那么YJQQQAQ会希望知道最接近煮熟的该种食物(即锅内存在时间最长的该种食物)还需要多少时间被煮熟。

3 l r:馋涎欲滴的SkyDec想知道,锅里编号在

[l,r][l,r]

之间的且熟了的食物总共有多少个。

输入输出格式

输入格式:
从标准输入读入数据。

本题包含多组数据,输入的第一行为一个正整数

TT

,表示数据组数。接下来依次描述每组数据,对于每组数据:

第一行一个正整数

nn

,表示食物的种类数。

第二行

nn

个用空格隔开的正整数

s1,s2,......sns_1,s_2,……s_n

,描述每种食物煮熟需要的时间。

第三行一个正整数

QQ

,表示事件的数目。

接下来

QQ

行,每行若干个用空格隔开的非负整数,描述一个事件。先是两个整数

t,opt,op

,分别表示发生事件的时间以及事件的类型。如果

op=0op=0

op=2op=2

,则接下来

11

个正整数

idid

,意义见题目描述;如果

op=1op=1

,则接下来没有其他数;如果

op=3op=3

,则接下来

22

个正整数

l,rl,r

,意义见题目描述。

我们保证

tt

按输入顺序严格递增。

我们保证

1t1091\leq t\leq 10^9

0op30\leq op\leq 3

1idn1\leq id\leq n

1lrn1\leq l\leq r\leq n

输出格式:
对于每个

op0op\neq 0

的操作,输出一行表示答案。对于不同的

opop

,需要输出的内容如下:

对于

op=1op=1

,如果Yazid成功取走食物,则输出他取走食物的编号;否则输出”Yazid is angry.”(不含引号,下同)。

对于

op=2op=2

,如果YJQQQAQ成功取走食物,则输出”Succeeded!”;否则,如果锅里有未煮熟的该类食物,输出最接近煮熟的该种食物还需要多少时间被煮熟;否则,输出”YJQQQAQ is angry.”。

对于

op=3op=3

,输出锅内编号在指定范围内的熟食的数量。

输出到标准输出。

输入输出样例

输入样例#1: 复制
输出样例#1: 复制

说明

 

对于所有数据,保证

T4T\leq 4

,保证

n100,000n\leq 100,000

Q500,000Q\leq 500,000

1si1081\leq s_i\leq 10^8

来自 CodePlus 2017 12 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit:idea/王聿中 命题/王聿中 验题/吕时清,杨景钦

Git Repo:https://git.thusaac.org/publish/CodePlus201712

感谢腾讯公司对此次比赛的支持。

一开始和leoly说我可以两棵splay搞搞 leoly说可以啊你写写看  还好我在飞机上又认真想了想发现可以用priority_queue搞定一棵 但还是差点险些tle xx

我首先询问的时候将每个东西煮熟的时间算好 放入优先队列 这时自动按照时间排序 然后每次询问我首先先将煮好的东西提取出来 插入splay中 在splay中我们按照这个下标排序 剩下我们要做的就是模拟他的操作 如果这个东西还没熟 我选择开一个vector来记录 一开始开deque 内存炸了 vector虽然不会自动回收内存 但是他可以将内存自动回收到stl中以便再次利用 还是挺高效方便的 注意需要清空priority_queue&我的vector 针对这个splay我每次需要求一个前驱后驱 什么的 常数就挺大的

leoly的线段树版本 就是我的splay其实完全可以替换为线段树或者树状数组拥有更多的常数优势 代码简短好写

 

分类: STL平衡树

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论