QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB Total points: 100
[+3]

# 4611. 简单数据结构

Statistics

参加完IOI2018之后就是姚班面试。而你,由于讨厌物理、并且想成为乔布斯一样的创业家,被成功踢回贵系。

转眼,时间的指针被指向2019,大二,12月初,考试周。

你早听学长说,数据结构期中考很难,对竞赛生不友好,集训队选手做不完卷子。

你冷笑。哼,堂堂国际金,这点难度的考试算什么。

两小时,你看完习题解析前五章所有内容,并且倒背如流;

一小时,你看了500页的讲义,并且记忆犹新;

十分钟,你骑车到考场,自信的你只带了一把水笔,虽然考试让带资料;

现在,摊开传说中神级卷子,你定神一看——

题目描述

给出一个长度为N的序列A1,A2,,AN,如果A中的一个子序列B1,B2,,BM,满足条件:

  • 1MN
  • 1i<MBi|Bi+1

那么称BA上升倍数子序列

现在有一个长度为 N 的序列 A 被初始化为A1,A2,,AN,以及Q次对序列A的操作。此处要求实现如下四种操作:

  • 0 x:在序列A的最左端插入一个数字x
  • 1 x:在序列A的最右端插入一个数字x
  • 2:移除序列A最左端的一个数字;
  • 3:移除序列A最右端的一个数字;

在初始化序列A每次操作之后,请计算此时序列A最长上升倍数子序列的长度MaxLen,以及所有长度为MaxLen的上升倍数子序列的不同的开头数Cnt,输出MaxLen和Cnt。

为了大幅度降低题目难度,保证在任意时刻序列A非空,其中的元素互不相等,并且均为1M之间的正整数;同一个数字最多只会被插入C次。

输入格式

从标准输入读入数据。

输入第一行包含三个正整数 N,M,Q,具体含义见上,保证 1N105NM1060Q105

输入第二行包含N个正整数,为A1,A2,,AN,保证1AiM,并且序列A中的元素互不相等;

接下来共Q行输入,每行输入格式形如0 x或者1 x或者2或者3,具体含义见上。

输出格式

输出到标准输出。

输出共Q+1行,在初始化和每次对序列A操作后,输出A中最长上升倍数子序列的长度MaxLen和所有长度为MaxLen的上升倍数子序列的不同的开头数Cnt,用一个空格隔开。

样例一

input

5 10 10
1 2 5 9 10
2
1 7
3
3
0 8
3
2
1 8
3
0 3

output

3 1
2 2
2 2
2 2
1 3
1 4
1 3
1 2
2 1
1 2
1 3

explanation

表格中以//隔开不同开头的最长上升子序列。

操作次数A输出答案可能的解释
01 2 5 9 103 11 2 10
12 5 9 10 2 22 10//5 10
22 5 9 10 72 22 10//5 10
32 5 9 10 2 22 10//5 10
42 5 9 1 32//5//9
58 2 5 9 1 42//5//8//9
68 2 5 1 32//5//8
72 5 1 22//5
82 5 8 2 12 8
92 5 1 22//5
103 2 5 1 32//3//5

限制与约定

对于所有的数据,有 1N105NM1060Q1051AiMC=10

下表展示了某些数据点的一些特殊约束,其中只有1表示只有形如1 x的操作,其他表述同理。

测试点编号约束条件
1,2,3N,Q100
4,5N,Q1000
6N=M1000
7Q=0
8只有0
9只有1
10只有2
11,12只有3
13只有0和1
14,15只有0和2
16只有1和3
17只有2和3
18,19,20无限制

后记

“奋战两小时,考个四五十”的表情包占领了你的朋友圈:

  • “啊,感觉自己人生完全了”
  • “但愿……我真的能拿到四五十”
  • “我考完了……考完了……完了”
  • “曾经以为是开玩笑的,原来我还是naïve了”

你冷笑。提前半小时交卷,你自然觉得,数据结构,满分,正常。