参加完IOI2018之后就是姚班面试。而你,由于讨厌物理、并且想成为乔布斯一样的创业家,被成功踢回贵系。
转眼,时间的指针被指向2019,大二,12月初,考试周。
你早听学长说,数据结构期中考很难,对竞赛生不友好,集训队选手做不完卷子。
你冷笑。哼,堂堂国际金,这点难度的考试算什么。
两小时,你看完习题解析前五章所有内容,并且倒背如流;
一小时,你看了500页的讲义,并且记忆犹新;
十分钟,你骑车到考场,自信的你只带了一把水笔,虽然考试让带资料;
现在,摊开传说中神级卷子,你定神一看——
题目描述
给出一个长度为N的序列A1,A2,⋯,AN,如果A中的一个子序列B1,B2,⋯,BM,满足条件:
- 1≤M≤N
- ∀1≤i<M,Bi|Bi+1
那么称B为A的上升倍数子序列
。
现在有一个长度为 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非空,其中的元素互不相等,并且均为1∼M之间的正整数;同一个数字最多只会被插入C次。
输入格式
从标准输入读入数据。
输入第一行包含三个正整数 N,M,Q,具体含义见上,保证 1≤N≤105,N≤M≤106,0≤Q≤105;
输入第二行包含N个正整数,为A1,A2,⋯,AN,保证1≤Ai≤M,并且序列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 | 输出答案 | 可能的解释 |
---|---|---|---|
0 | 1 2 5 9 10 | 3 1 | 1 2 10 |
1 | 2 5 9 10 | 2 2 | 2 10//5 10 |
2 | 2 5 9 10 7 | 2 2 | 2 10//5 10 |
3 | 2 5 9 10 | 2 2 | 2 10//5 10 |
4 | 2 5 9 | 1 3 | 2//5//9 |
5 | 8 2 5 9 | 1 4 | 2//5//8//9 |
6 | 8 2 5 | 1 3 | 2//5//8 |
7 | 2 5 | 1 2 | 2//5 |
8 | 2 5 8 | 2 1 | 2 8 |
9 | 2 5 | 1 2 | 2//5 |
10 | 3 2 5 | 1 3 | 2//3//5 |
限制与约定
对于所有的数据,有 1≤N≤105,N≤M≤106,0≤Q≤105,1≤Ai≤M,C=10。
下表展示了某些数据点的一些特殊约束,其中只有1
表示只有形如1 x
的操作,其他表述同理。
测试点编号 | 约束条件 |
---|---|
1,2,3 | N,Q≤100 |
4,5 | N,Q≤1000 |
6 | N=M≤1000 |
7 | Q=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了”
你冷笑。提前半小时交卷,你自然觉得,数据结构,满分,正常。