題意 ：

• 維護一個“雙端隊列”，1e7次操作，支持左插入，右插入，按值刪除，查找中點（靠右）值$ceil[(m+1)/2]$，值不重復。

思路 ：

• 1e7所以所有操作都要滿足$O(1)$
• deque不論是front,back,push_front,push_back,pop_front,pop_back都是$O(1)$
• 查詢中間位置，因此想到用兩個雙端隊列維護，由于每次只插入一個數，不難維護前后者長度一樣
• 刪除操作，由于插入的值$1?1e7$，可以使用數組記錄每個數屬于哪個雙端隊列，刪除時直接將vis改為0且更新對應雙端隊列的長度即可，查詢時只要先將在右雙端隊列左端前vis == 0的值去掉即可，注意刪除后也要維護兩個雙端隊列長度一致。

#include <iostream> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <vector> #include <unordered_map> #include <unordered_set> #include <set> #include <map> #include <stack> #include <queue> #include <deque> #include <ctime> #define endl '\n' #define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define lowbit(x) (x&-x) using namespace std; const double pi = acos(-1); typedef long long ll; typedef pair<int, int> PII; typedef pair<long, long> PLL;const int N = 1e7 + 10;int vis[N], tot; deque<int> lq, rq; int lc, rc; // 記錄不用糾結vis數組的非真實情況的左右雙端隊列的長度// 每次修改長度后，維護lc == rc / lc + 1 == rc void del() {// 左雙端隊列比右雙端隊列大while (lc > rc){while (vis[lq.back()] == 0) lq.pop_back();rq.push_front(lq.back());lq.pop_back();vis[rq.front()] = 2;lc -- , rc ++ ;}// 右雙端隊列比左雙端隊列+1還大while (rc > lc + 1){while (vis[rq.front()] == 0) rq.pop_front();lq.push_back(rq.front());rq.pop_front();vis[lq.back()] = 1;lc ++ , rc -- ;} }int main() {IOS;int q;cin >> q;while (q -- ){string op;cin >> op;if (op == "L"){lq.push_front( ++ tot);vis[tot] = 1;lc ++ ;del();}else if (op == "R"){rq.push_back( ++ tot);vis[tot] = 2;rc ++ ;del();}else if (op == "G"){int x;cin >> x;if (vis[x] == 1) lc -- ;if (vis[x] == 2) rc -- ;vis[x] = 0;del();}else{while (vis[rq.front()] == 0) rq.pop_front();cout << rq.front() << endl;}}return 0; }

總結

以上是生活随笔為你收集整理的Boring data structure problem 模拟-双端队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。