先赞后看，养成习惯。小编肝了好几个小时，麻烦给个点赞关注收藏好不好
题目描述
参加完IOI2018之后就是姚班面试。而你，由于讨厌物理、并且想成为乔布斯一样的创业家，被成功踢回贵系。
转眼，时间的指针被指向2019，大二，12月初，考试周。
你早听学长说，数据结构期中考很难，对竞赛生不友好，集训队选手做不完卷子。
你冷笑。哼，堂堂国际金，这点难度的考试算什么。
两小时，你看完习题解析前五章所有内容，并且倒背如流；
一小时，你看了500页的讲义，并且记忆犹新；
十分钟，你骑车到考场，自信的你只带了一把水笔，虽然考试让带资料；
现在，摊开传说中神级卷子，你定神一看——
给出一个长度为 NNN 的序列 A1,A2,⋯ ,ANA_1,A_2,\\cdots,A_NA1,A2,⋯,AN，如果 AAA 中的一个子序列 B1,B2,⋯ ,BMB_1,B_2,\\cdots,B_MB1,B2,⋯,BM，满足条件：
1≤M≤N1 \\le M \\le N1≤M≤N
∀1≤i≤M1 \\le i \\le M1≤i≤M，BiB_iBi|Bi+1B_{i+1}Bi+1
那么称 BBB 为 AAA 的上升倍数子序列。
现在有一个长度为 NNN 的序列 AAA 被初始化为 A1,A2,⋯ ,ANA_{1},A_{2},\\cdots,A_{N}A1,A2,⋯,AN，以及 QQQ 次对序列 AAA 的操作。此处要求实现如下四种操作：
0 x：在序列 AAA 的最左端插入一个数字 xxx；
1 x：在序列 AAA 的最右端插入一个数字 xxx；
2：移除序列 AAA 最左端的一个数字；
3：移除序列 AAA 最右端的一个数字；
在初始化序列 AAA 和每次操作之后，请计算此时序列 AAA 中最长上升倍数子序列的长度 MaxLen\\mathrm{MaxLen}MaxLen，以及所有长度为 MaxLen\\mathrm{MaxLen}MaxLen 的上升倍数子序列的不同的开头数 Cnt\\mathrm{Cnt}Cnt，输出 MaxLen\\mathrm{MaxLen}MaxLen 和 Cnt\\mathrm{Cnt}Cnt。
为了大幅度降低题目难度，保证在任意时刻序列 AAA 非空，其中的元素互不相等，并且均为 1∼M1\\sim M1∼M 之间的正整数；同一个数字最多只会被插入 CCC 次。
输入格式
输入第一行包含三个正整数 N,M,QN,M,QN,M,Q，具体含义见上，保证 1≤N≤1051\\le N \\le 10^51≤N≤105，N≤M≤106N \\le M \\le 10^6N≤M≤106，0≤Q≤1050\\le Q \\le 10^50≤Q≤105；
输入第二行包含 NNN 个正整数，为 A1,A2,⋯ ,ANA_1,A_2,\\cdots,A_NA1,A2,⋯,AN，保证 1≤Ai≤M1\\le A_i\\le M1≤Ai≤M，并且序列 AAA 中的元素互不相等；
接下来共 QQQ 行输入，每行输入格式形如0 x或者1 x或者2或者3，具体含义见上。
输出格式
输出共 Q+1Q+1Q+1 行，在初始化和每次对序列 AAA 操作后，输出 AAA 中最长上升倍数子序列的长度 MaxLen\\mathrm{MaxLen}MaxLen 和所有长度为 MaxLen\\mathrm{MaxLen}MaxLen 的上升倍数子序列的不同的开头数 Cnt\\mathrm{Cnt}Cnt，用一个空格隔开。
输入输出样例 #1
输入 #1
5 10 10
1 2 5 9 10
2
1 7
3
3
0 8
3
2
1 8
3
0 3
输出 #1
3 1
2 2
2 2
2 2
1 3
1 4
1 3
1 2
2 1
1 2
1 3
说明/提示
样例解释
表格中以//隔开不同开头的最长上升子序列。
对于所有的数据，有 1≤N≤1051\\le N \\le 10^51≤N≤105，N≤M≤106N\\le M \\le 10^6N≤M≤106，0≤Q≤1050\\le Q \\le 10^50≤Q≤105，1≤Ai≤M1\\le A_i\\le M1≤Ai≤M，C=10C=10C=10。
下表展示了某些数据点的一些特殊约束，其中只有1表示只有形如1 x的操作，其他表述同理。
后记
“奋战两小时，考个四五十”的表情包占领了你的朋友圈：
“啊，感觉自己人生完全了”
“但愿……我真的能拿到四五十”
“我考完了……考完了……完了”
“曾经以为是开玩笑的，原来我还是naïve了”
你冷笑。提前半小时交卷，你自然觉得，数据结构，满分，正常。
【题目解析】
一、整体架构
这是一个动态维护最长上升倍数子序列的解决方案，使用了双端队列数据结构，在队列两端插入/删除时增量更新统计信息，而不是重新计算整个序列。
二、核心数据结构
1. 双端队列实现
int data[MAXN]; // 队列数据
int left, right; // 左右指针
- left和right初始设为中间位置，向两边扩展
- 支持四种操作：前端插入、后端插入、前端删除、后端删除
2. 关键状态数组
int pos[MAXM]; // pos[x] = 数字x在队列中的下标，0表示不存在
int f[MAXN]; // f[i] = 以下标i开头的最大子序列长度
int g[MAXN][MAXLOG]; // g[i][j] = 以下标i开头，长度为j的序列数量
int fcnt[MAXLOG]; // fcnt[len] = 全局统计中长度为len的开头数量
三、核心算法思想
1. 状态定义
- f[i]：以位置i的元素开头的最长上升倍数子序列长度
- g[i][j]：以位置i的元素开头，长度为j的序列数量
2. 重要递推关系
对于任意位置i：
- 那么g[i][f[j]+1] += g[j][f[j]]
- 即：从i开头，接上j开头的最长序列
3. 全局统计
- fcnt[len]：统计所有f[i] = len的i的个数
- 答案就是最大的len使得fcnt[len] > 0，以及对应的fcnt[len]
四、四大操作的实现逻辑
1. pushFront(val) – 前端插入
1. left—，val放在data[left]
2. 初始化：g[left][1] = 1
3. 遍历val的所有倍数multiple：
– 如果multiple存在于队列中（pos[multiple]存在）
– 更新：g[left][f[pos[multiple]] + 1]++
4. 计算f[left] = 最大的j使得g[left][j] > 0
5. fcnt[f[left]]++
关键理解：新元素在最前面，它后面所有的元素都可能成为它的后继。我们只需要考虑它的倍数。
2. pushBack(val) – 后端插入
1. right++，val放在data[right]
2. 初始化：g[right][1] = 1
3. 先把自己的贡献加入全局统计
4. 获取val的所有因子
5. 对每个因子factor：
a. 如果factor在队列中
b. 重新计算factor的f值（因为它可能接上新的val）
c. 如果f值变化，更新全局统计
关键理解：新元素在最后面，它可能成为前面某些元素的后继。需要更新所有能整除它的数（即它的因子）。
3. 删除操作
- popFront()：比较简单，只需移除该位置的贡献
- popBack()：类似pushBack的逆操作，需要重新计算受影响因子的f值
五、关键技术细节
1. 因子遍历优化
// 只遍历到sqrt(val)，同时获取一对因子
for (int i = 1; i <= sqrt_val; i++) {
if (val % i == 0) {
// i 是一个因子
// val/i 是另一个因子（当i*i != val时）
}
}
2. g数组的更新逻辑
// 当val插入时，对于每个因子factor（factor能整除val）
if (pos[factor] && pos[factor] < pos[val]) {
// factor在val前面
// 从factor可以接上val
g[pos[factor]][f[pos[val]] + 1]++;
}
3. 重新计算f值
// 找到最大的j使得g[i][j] > 0
for (int j = MAXLOG–1; j >= 1; j—) {
if (g[i][j]) {
f[i] = j;
break;
}
}
六、时间复杂度分析
每个操作的时间复杂度主要来自：
由于m≤10⁶，这个复杂度是可接受的。
七、示例说明
假设队列：[2, 4, 8]
初始状态：
- pos[2]=1, pos[4]=2, pos[8]=3
- f[3]=1 (只有8)
- f[2]=2 (4→8)
- f[1]=3 (2→4→8)
插入3到前端：
- 检查3的倍数：6,9,12,…（都不在队列中）
- f[新位置]=1
插入12到后端：
- 12的因子：1,2,3,4,6,12
- 检查因子2（位置1）：2|12成立，更新f[1]可能变为4
- 检查因子4（位置2）：4|12成立，更新f[2]可能变为3
