特殊队列

双端队列

双端队列是指一个可以在队首/队尾插入或删除元素的队列。相当于是栈与队列功能的结合。具体地，双端队列支持的操作有 4 个：

• 在队首插入一个元素
• 在队尾插入一个元素
• 在队首删除一个元素
• 在队尾删除一个元素

数组模拟双端队列的方式与普通队列相同。

C++ STL 中的双端队列

C++ 在 STL 中也提供了一个容器 std::deque，使用前需要先引入 <deque> 头文件。 STL 中的 deque 容器提供了一众成员函数以供调用。其中较为常用的有：

• 元素访问
  • q.front() 返回队首元素
  • q.back() 返回队尾元素
• 修改
  • q.push_back() 在队尾插入元素
  • q.pop_back() 弹出队尾元素
  • q.push_front() 在队首插入元素
  • q.pop_front() 弹出队首元素
  • q.insert() 在指定位置前插入元素（传入迭代器和元素）
  • q.erase() 删除指定位置的元素（传入迭代器）
• 容量
  • q.empty() 队列是否为空
  • q.size() 返回队列中元素的数量

此外，deque 还提供了一些运算符。其中较为常用的有：

• 使用赋值运算符 = 为 deque 赋值，类似 queue。
• 使用 [] 访问元素，类似 vector。

<queue> 头文件中还提供了优先队列 std::priority_queue，因其与 堆 更为相似，在此不作过多介绍。

循环队列

使用数组模拟队列会导致一个问题：随着时间的推移，整个队列会向数组的尾部移动，一旦到达数组的最末端，即使数组的前端还有空闲位置，再进行入队操作也会导致溢出（这种数组里实际有空闲位置而发生了上溢的现象被称为「假溢出」）。

解决假溢出的办法是采用循环的方式来组织存放队列元素的数组，即将数组下标为 0 的位置看做是最后一个位置的后继。（数组下标为 x 的元素，它的后继为 (x + 1) % SIZE）。这样就形成了循环队列。

#include
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
using namespace std;
/******************heading******************/
const int M = 5e4 + 5, P = 505;  // 定义常数
int I, m, p;

int _(int d) { return (d + p) % p; }  // 用于取模

namespace DQ {                // 双栈模拟双端队列
pair<int, int> fr[M], bc[M];  // 二元组，详见题目3.4
int tf = 0, tb = 0;           // 一端的top,因为是双端队列所以有俩
int ff[M][P], fb[M][P];

void update(pair<int, int> *s, int f[][P], int i) {  // 用f[i-1]更新f[i]
for (int j = 0; j <= (p - 1); j++) {
f[i][j] = f[i - 1][j];
if (~f[i - 1][_(j - s[i].first)])  // 按位取反
f[i][j] = max(f[i][j], f[i - 1][_(j - s[i].first)] + s[i].second);
}
}

// 以下两行代码表示push入队列，很好理解
void push_front(pair<int, int> x) { fr[++tf] = x, update(fr, ff, tf); }

void push_back(pair<int, int> x) { bc[++tb] = x, update(bc, fb, tb); }

// 以下两行代码表示从队列pop出元素
void pop_front() {
if (tf) {
--tf;
return;
}
int mid = (tb + 1) / 2, top = tb;
for (int i = mid; i >= 1; i--) push_front(bc[i]);
tb = 0;
for (int i = (mid + 1); i <= top; i++) push_back(bc[i]);
--tf;
// 上面的代码，逻辑和普通队列是一样的
}

void pop_back() {
if (tb) {
--tb;
return;
}
int mid = (tf + 1) / 2, top = tf;
for (int i = mid; i >= 1; i--) push_back(fr[i]);
tf = 0;
for (int i = (mid + 1); i <= top; i++) push_front(fr[i]);
--tb;
// 上面的代码，逻辑和普通队列是一样的
}

int q[M], ql, qr;  // 题目任务5要求的

int query(int l, int r) {
const int *const f = ff[tf], *const g = fb[tb];
int ans = -1;
ql = 1, qr = 0;
for (int i = (l - p + 1); i <= (r - p + 1); i++) {
int x = g[_(i)];
while (ql <= qr && g[q[qr]] <= x) --qr;
q[++qr] = _(i);
}
for (int i = (p - 1); i >= 0; i--) {
if (ql <= qr && ~f[i] && ~g[q[ql]]) ans = max(ans, f[i] + g[q[ql]]);
// 删 l-i，加 r-i+1
if (ql <= qr && _(l - i) == q[ql]) ++ql;
int x = g[_(r - i + 1)];
while (ql <= qr && g[q[qr]] <= x) --qr;
q[++qr] = _(r - i + 1);
}
return ans;
}

void init() {
for (int i = 1; i <= (P - 1); i++) ff[0][i] = fb[0][i] = -1;
}  // 初始化
}  // namespace DQ

int main() {
DQ::init();
scanf("%d%d%d", &I, &m, &p);
for (int i = 1; i <= m; i++) {
char op[5];
int x, y;
scanf("%s%d%d", op, &x, &y);
if (op[0] == 'I' && op[1] == 'F')
DQ::push_front(make_pair(_(x), y));
else if (op[0] == 'I' && op[1] == 'G')
DQ::push_back(make_pair(_(x), y));
else if (op[0] == 'D' && op[1] == 'F')
DQ::pop_front();
else if (op[0] == 'D' && op[1] == 'G')
DQ::pop_back();
else
printf("%d\n", DQ::query(x, y));
}
return 0;
}