2021“MINIEYE杯”中国大学生算法设计超级联赛（9） Boring data structure problem

2021“MINIEYE杯”中国大学生算法设计超级联赛（9） Boring data structure problem 模拟

Problem Analysis

按题目要求维护一个双端队列，每次寻找中位数的值输出。显然需要每个操作在 O ( 1 ) O(1) O(1)内完成，因此按照原题意去维护是行不通的…那么考虑如何维护。

我们可以开两个队列。用第二个队列的首元素表示中位数下标元素。那么我们只需要在每次操作后对俩个序列的长度进行维护，使得 q u e u e 1 queue_1 queue1​的长度 = q u e u e 2 queue_2 queue2​的长度+ 1 1 1即可。

AC Code

#include 
using namespace std;

const int maxn = 1e7 + 10;
int vis[maxn], tot, lsize, rsize;
deque lq, rq;

inline void del(){
    while(lsize > rsize){
        while(vis[lq.back()] == 0) lq.pop_back();
        rq.push_front(lq.back());
        lq.pop_back();
        rsize++, lsize--;
        vis[rq.front()] = 2;
    }
    while(rsize - 1 > lsize){
        while(vis[rq.front()] == 0) rq.pop_front();
        lq.push_back(rq.front());
        rq.pop_front();
        lsize++, rsize--;
        vis[lq.back()] = 1;
    }
}


signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 0; cin >> t;
    while(t--){
        char op; cin >> op;
        if(op == 'L'){
            lq.push_front(++tot);
            vis[tot] = 1, lsize++;
            del();
        }
        else if(op == 'R'){
            rq.push_back(++tot);
            vis[tot] = 2;
            rsize++;
            del();
        }
        else if(op == 'G'){
            int x = 0; cin >> x;
            if(vis[x] == 1) lsize--;
            else if(vis[x] == 2) rsize--;
            vis[x] = 0;
            del();
        }
        else if(op == 'Q'){
            while(vis[rq.front()] == 0) rq.pop_front();
            cout