4338: 「清华集训 2017」简单数据结构
内存限制：1024 MB
时间限制：3.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
参加完 IOI2018 之后就是姚班面试。而你，由于讨厌物理、并且想成为乔布斯一样的创业家，被成功踢回贵系。
转眼，时间的指针被指向 2019，大二，12 月初，考试周。
你早听学长说，数据结构期中考很难，对竞赛生不友好，集训队选手做不完卷子。
你冷笑。哼，堂堂国际金，这点难度的考试算什么。
两小时，你看完习题解析前五章所有内容，并且倒背如流；
一小时，你看了 500 页的讲义，并且记忆犹新；
十分钟，你骑车到考场，自信的你只带了一把水笔，虽然考试让带资料；
现在，摊开传说中神级卷子，你定神一看——
给出一个长度为 $N$ 的序列 $A_{1},A_{2},\cdots,A_{N}$ ，如果 $A$ 中的一个子序列 $B_1,B_2,\cdots,B_M$，满足条件：
- $1\le M\le N$
- $\forall 1\le i
输入
输入第一行包含三个正整数 $N,M,Q$，具体含义见上，保证 $1\le N \le 10^5$，$N\le M \le 10^6$，$0\le Q \le 10^5$；
输入第二行包含 $N$ 个正整数，为 $A_1,A_2,\cdots,A_N$，保证 $1\le A_i\le M$，并且序列 $A$ 中的元素互不相等；
接下来共 $Q$ 行输入，每行输入格式形如`0 x`或者`1 x`或者`2`或者`3`，具体含义见上。
输出
输出共 $Q+1$ 行，在初始化和每次对序列 $A$ 操作后，输出 $A$ 中最长上升倍数子序列的长度 $\mathrm{MaxLen}$ 和所有长度为 $\mathrm{MaxLen}$ 的上升倍数子序列的不同的开头数 $\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提示
数据范围：对于所有的数据，有 $1\le N \le 10^5$，$N\le M \le 10^6$，$0\le Q \le 10^5$，$1\le A_i\le M$，$C=10$。 下表展示了某些数据点的一些特殊约束，其中`只有1`表示只有形如`1 x`的操作，其他表述同理。 | 测试点编号 | 约束条件 | |:-:|:-:| | 1,2,3 | $N,Q\le 100$ | | 4,5 | $N,Q\le 1000$ | | 6 | $N=M\le 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* 了。」 你冷笑。提前半小时交卷，你自然觉得，数据结构，满分，正常。