队列进阶数据结构

一、基本队列

相对等效

对于给定的一个序列，如果每次操作都需要改变大部分数据，数学运算一个相同的算子，而只有少部分数据不需要改变；则可以通过逆向改变少部分数据，赋予一个逆算子，进行相应运算化简，记录相对差量，最终换算为数据结果。

应用

分析思路：


其中应当证明在依次选取 $x_1, x_2$ 时，对应的第一秒后 $[px_1], x_1-[px_1], x_2+q$，在 $x_2$ 的一秒后 $[px_1]+q, x_1-[px_1]+q, [p(x_2+q)], (x_2+q)-[p(x_2+q)]$，则易证 $[px_1]+q > [p(x_2+q)]$， $x_1-[px_1]+q > (x_2+q)-[p(x_2+q)]$，进而推广到任意两段满足 $x_1 >= x_2$ 时，只要 $x_1$ 在 $x_2$ 之前被取出，不论之后是否接着取 $x_2$，还是直接取 $x_1$ 分出的两端，或是其他段，都等效于最开始的 $x_2$。

二、单调队列——基于双端队列

单调队列是指队列中元素之间的关系始终保持单调性，而且队首和队尾都可以进行出队操作，只有队尾可以进行入队操作。（注意是始终保持）
单调队列功能：在每次加入或者删除元素时都保持序列里的元素有序，即队首元素始终是最小值或者最大值。

最大子序和——单调队列算法

最优策略集合：下标位置递增、对应的前缀和 S的值也递增

int l = 1, r = 1;  // l指向队头，r指向队尾
q[1] = 0;       // 保存决策的基于数组的模拟队列
for(int i=1;i<=n;i++){   // 枚举最右端节点i
	// Step 1:
	while(l <= r && (i - q[l]) > m) l++; // 边界判断，最多只能选m个数，否则队首出队
	// Step 2:
	ans = max(ans, sum[i]-sum[q[l]]); // 寻找最大值，sum[]表示数组前缀和
	// Step 3:
	while(l <= r && sum[q[r]] >= sum[i]) r--;  //更新，删除不小于i结点对应的队列元素
	q[++r] = i;
}

时间复杂度：$O(N)$
注解：

• $Step 1$：检查队首，如果队首指向的下标小于等于 $i-m$，即相对于 $i$ 而言，队首的元素已经跑出区间 $[i-m+1, i]$，子序列长度超过了 $m$，那么弹出队首元素，对应操作 $l++$；对最大连续子序列和问题而言，在上一轮中队首元素对应的最长子序列的和已经计算并比较存入 $ans$ 中，此时进入新元素后，队首元素已经属于无效元素，所以直接出队；
• $Step 2$：相对于右端点 $i$ 而言，队首元素 $q[l]$ 对应的便是最优左端点 $j$；
• $Step 3$：检查队尾，如果队尾元素大于或等于要添加的值，则弹出队尾元素，对应操作 $r- -$，目的就是保持队首元素一直是最小值，且队列单调；
• $Step 4$：更新队尾，$q[++r]=i$，首先 $++r$ 为新元素腾出位置，加入元素的下标；解释：
  • 根据前面分析的结论，以相对于右端点 $i$ 来看，如果 $sum[q[r]] >= sum[i]$，最大连续子序列和一定不会是 $q[r]$ 对应的元素节点,因为此时 $sum[q[l]] <= sum[q[r]]$，比较而言 $q[l]$ 更优；
  • 如果不弹出 $q[r]$,那么当 $q[l]==q[r]$ 时，此时会出现 $sum(q[l]) >= sum(q[l+1])$,很明显在这种条件下，决策 $q[l+1]$ 优于决策 $q[l]$，因为相对于右端点 $i$ 选 $q[l+1]$ 可以获得不劣于 $q[l]$ 的最大连续和，因此没有必要保留 $q[r]$;
  • $q[i]$ 替换 $q[r]$ 机制，当需要弹出队尾元素 $q[r]$ 时，$r- -$ 之后 $Step 4$ 再次更新序列对应元素处在队列中的决策下标为新元素节点 $q[i]$，当下一轮 $l==r$ 时，$q[l]=q[i]$ 直接索引下一元素的下标；

单调队列思想：在决策集合（队列）中及时排除一定不是最优解的选择。
单调队列模板：

int data[N+1];    // 原始数据序列集合
int q[N];       // 用于模拟单调队列的数组
int k = Nnum;    // 支持的最大区间长度
int head = 1,tail = 1;   // 初始队列没有元素
for(int i=1;i<=N;i++){
	while(head <= tail and q[head] <= i - k) head++; //队首检查：保证队列长度合法
	while(head <= tail and data[q[tail]] >= data[i]) tail--; // 队尾检查：保证队列单调性
	q[++tail] = i; //插入新元素
}