UOJ Logo Universal Online Judge

UOJ

#341. 【清华集训2017】简单数据结构

统计

题目背景

参加完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 < M$,$B_i\Big{|}B_{i+1}$

那么称$B$为$A$的上升倍数子序列

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

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

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

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

输入格式

从标准输入读入数据。

输入第一行包含三个正整数 $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$中最长上升倍数子序列的长度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

限制与约定

对于所有的数据,有 $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无限制

时间限制:$3\texttt{s}$

空间限制:$1\texttt{GB}$

后记

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

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

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

下载

样例数据下载