#P4224. [清华集训2017] 简单数据结构

[清华集训2017] 简单数据结构

题目描述

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

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

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

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

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

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

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

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

给出一个长度为 NN 的序列 A1,A2,,ANA_1,A_2,\cdots,A_N,如果 AA 中的一个子序列 B1,B2,,BMB_1,B_2,\cdots,B_M,满足条件:

1MN1 \le M \le N

1iM1 \le i \le MBiB_i|Bi+1B_{i+1}

那么称 BBAA 的上升倍数子序列。

现在有一个长度为 NN 的序列 AA 被初始化为 A1,A2,,ANA_{1},A_{2},\cdots,A_{N},以及 QQ 次对序列 AA 的操作。此处要求实现如下四种操作:

0 x:在序列 AA 的最左端插入一个数字 xx

1 x:在序列 AA 的最右端插入一个数字 xx

2:移除序列 AA 最左端的一个数字;

3:移除序列 AA 最右端的一个数字;

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

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

输入格式

输入第一行包含三个正整数 N,M,QN,M,Q,具体含义见上,保证 1N1051\le N \le 10^5NM106N \le M \le 10^60Q1050\le Q \le 10^5

输入第二行包含 NN 个正整数,为 A1,A2,,ANA_1,A_2,\cdots,A_N,保证 1AiM1\le A_i\le M,并且序列 AA 中的元素互不相等;

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

输出格式

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

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

提示

样例解释

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

对于所有的数据,有 1N1051\le N \le 10^5NM106N\le M \le 10^60Q1050\le Q \le 10^51AiM1\le A_i\le MC=10C=10

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

后记

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

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

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