#2007. 简单数据结构

    ID: 2007 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest488来源:qoj.ac数据:公开样例线段树平衡树二分

简单数据结构

简单数据结构

题目描述

标题: 简单数据结构 - Problem - QOJ.ac

Statistics

The problem was used in the following contests:

参加完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输出答案可能的解释01 2 5 9 103 11 2 1012 5 9 10 2 22 10//5 1022 5 9 10 72 22 10//5 1032 5 9 10 2 22 10//5 1042 5 9 1 32//5//958 2 5 9 1 42//5//8//968 2 5 1 32//5//872 5 1 22//582 5 8 2 12 892 5 1 22//5103 2 5 1 32//3//5

限制与约定

对于所有的数据,有 1≤N≤105,N≤M≤106,0≤Q≤105,1≤Ai≤M,C=10。

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

测试点编号约束条件1,2,3N,Q≤1004,5N,Q≤10006N=M≤10007Q=08只有09只有110只有211,12只有313只有0和114,15只有0和216只有1和317只有2和318,19,20无限制

后记

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

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

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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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