Skip to content

11601: 【原1601】基础数据结构

题目

题目描述

author: Chika 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1601

Description

你将要实现一个十分基础的数据结构。 这个数据结构模型是一个单向循环链表,其中,1连向2, 2连向3... n将连向1。 数据结构的维护过程中常伴随着删除操作,以及询问某个节点的前驱或者后继。

嘛,这样的数据结构好像并不够浪漫。

于是这个数据结构中,每个节点会附带上权值。

查询最大值似乎已经成为了一种惯用的套路。这次也不例外,你需要不时回答当前数据结构所有未被删除的节点的最大权值。

你的努力并不总是得不到回报。如果你能用一种足够优美的方式解决这个题,那么作为奖励,你将会获得一枚蜜柑糖哦♪

Input Format

第一行是一个数n,表示这个数据结构初始的节点个数。

第二行将会读入n个非负整数,依次为这n个节点所带的权值。

第三行是一个数q,代表可能的事件数。

接下来q行,每一行代表一种可能的事件。

  • 0 x: 表示删除编号为x的节点,特别的,如果x已经被删除,你应当忽略掉这个无意义的事件。
  • 1 P x: 询问编号为x的前驱节点编号,如果x已经被删除,你应当输出"Invalid."(不带引号)。
  • 1 N x: 询问编号为x的后继节点编号,同上,如果x已经被删除,输出"Invalid."(不带引号)。
  • 2: 询问此时未删除节点中的最大权值。特别的,如果此时这个数据结构被删空了,也应当输出"Invalid."(不带引号)。

关于前驱后继的特别定义: 一般情况下,如果一个循环链表中只有一个元素,其前驱后继均应视作该节点本身。

Output Format

对于每一个询问类事件,输出对应的答案或者是"Invalid."(不带引号) 。

Sample Input

2
1 2
2
1 P 1
2

Sample Output

2
2

Limits

  • 对于40%的数据,n, q <= 1000
  • 对于另外20%的数据,n, q <= 1000000,没有询问最大值操作。
  • 对于80%的数据,n, q <= 1000000
  • 对于100%的数据,n, q <= 6000000, 每个点的权值0 <= w_i <= 10^9

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!