#2326. 「清华集训 2017」简单数据结构

内存限制:1024 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: spj

题目描述

参加完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
  • 1i<M\forall 1\le i<M B_i\Big{|}B_{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

样例解释

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

操作次数 AA 输出答案 可能的解释
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

数据范围与提示

对于所有的数据,有 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的操作,其他表述同理。

测试点编号 约束条件
1,2,3 N,Q100N,Q\le 100
4,5 N,Q1000N,Q\le 1000
6 N=M1000N=M\le 1000
7 Q=0Q=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了”

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