Codeforces Round #366 (Div. 2) C. Thor 数据结构、队列优化

Source

Codeforces Round #366 (Div. 2)

My Solution

数据结构、队列优化

queue<pair<int, int> > que;            //用来存放应该 操作3 后 剩余的通知
queue v[maxn];                     //v[i]用来存放，剩余的未读的应用 i 的通知

所有通知 在que里入队一次出队一次， 在v[maxn]里入队一次出队一次， 总复杂度 2*n， 所以

复杂度 O(n)

此外 这里输出的东西 比较多， 用 cout << cnt << endl; 的运行时间 大约 是 cout << cnt << "n";  不到一点2倍，

所以以后遇到输出的东西 比较多的时候就用 “n”， 其它普通的时候还是用 endl好了， 毕竟 endl打起来快且安全

#include 
#include 
#include 
using namespace std;
typedef long long LL;
const int maxn = 3*1e5 + 8;

queue<pair<int, int> > que;
queue v[maxn];

int main()
{
    #ifdef LOCAL
    freopen("c.txt", "r", stdin);
    //freopen("o.txt", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, q, op, val, cnt = 0,ptr = 0, type;
    cin >> n >> q;
    for(int i = 0; i < q; i++){ cin >> op >> val;
        if(op == 1){
            que.push(make_pair(ptr, val));
            v[val].push(ptr);
            cnt++;
            ptr++;
        }
        else if(op == 2){
            cnt -= v[val].size();
            while(!v[val].empty()) v[val].pop();
        }
        else{
            while(!que.empty() && que.front().first < val){
                type = que.front().second;
                if(!v[type].empty() && v[type].front() == que.front().first){
                    cnt--;
                    v[type].pop();
                    que.pop();
                }
                else{
                    que.pop();
                }
            }

        }
        cout << cnt << "n";
    }

    #ifdef LOCAL
    while(!que.empty()) que.pop();
    for(int i = 0; i <= n; i++){
        while(!v[i].empty()) v[i].pop();
    }
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx