P4032 solution

Areka6219 · 2021-08-10 17:11:43 · 题解

题意

• 我们把食物分为两个集合，熟的为 S_1，不熟为 S_2。

分析

• 提供思路：树状数组+两个优先队列+一个双端队列（可能有点十分麻烦）。
• 首先针对 Ask_3 我们自然可以想到树状数组。
• 接下来我们想如何维护 Add_0、Ask_1、Ask_2、S_1、S_2。
• 可以想到，用优先队列维护 S_2​，在每次查询前将队列中的元素放进 S_1​ 的优先队列。
• 这里的两个优先队列排序的关键字不同，S_1 的优先队列，第一关键字为编号，因为已经成熟，S_2 的优先队列第一关键字为成熟时间，因为我们要贪心的判断是否成熟
• 对于 Add_0 我们直接模拟即可，用 deque 来维护编号的信息，并注意更新树状数组。
• 对于 Ask_1 我们查询 S_1​ 所对应的优先队列是否为空，若不为空，输出队首即可。
• 对于 Ask_2​ 我们查询编号对应的 deque 是否为空，直接模拟即可，注意运用懒惰删除法更新优先队列（不懂的可以看 Dijkstra 的题解，这边请）。
• 对于 Ask_3 使用树状数组直接干碎即可。

吐槽

怎么会有卡空间这档子破事.jpg

原来是我写挂了.jpg

关于一个题交了4页这档子破事

Code

const int maxn = 1e5 + 1;

int n, tot, a[maxn];
bool vis[500001];

class Tree_Array {
    private:
        int t[maxn];

        inline int lowbit(int x) {
            return x & (-x);
        }

    public:

        inline void init() {
            memset(t, 0, sizeof(t));
        }

        inline void Add(int pos, int v) {
            while(pos <= n)
                t[pos] += v, pos += lowbit(pos);
        }

        inline int Ask(int pos) {
            int res = 0;
            while(pos)
                res += t[pos], pos -= lowbit(pos);
            return res;
        }
};

Tree_Array T;

class Node {
    public:
        int id, nid, tm;
        inline friend bool operator < (const Node &a, const Node &b) {
            if(a.id == b.id)
                return a.tm > b.tm;
            else
                return a.id > b.id;
        }
        Node() {}
        Node(int i, int i1, int t) : id(i), nid(i1), tm(t) {}
};

class Node1 {
    public:
        int id, nid, tm;
        inline friend bool operator < (const Node1 &a, const Node1 &b) {
            if(a.tm == b.tm)
                return a.id > b.id;
            else
                return a.tm > b.tm;
        }
        Node1() {}
        Node1(int i, int i1, int t) : id(i), nid(i1), tm(t) {}
};

class Node2 {
    public:
        int nid, tm;
        Node2() {}
        Node2(int i1, int t) : nid(i1), tm(t) {}
};

priority_queue <Node> Q1;
priority_queue <Node1> Q2;

deque <Node2> v[maxn];

inline void init() {
    tot = 0;
    memset(vis, 0, sizeof(vis));
    while(!Q1.empty())
        Q1.pop();
    while(!Q2.empty())
        Q2.pop();
    for(int i = 1; i < maxn; ++i)
        while(!v[i].empty())
            v[i].pop_front();
    T.init();
}
signed main() {
    int ss = read();
    while(ss--) {
        init();
        n = read();
        for(int i = 1; i <= n; ++i)
            a[i] = read();
        int Qs = read();
        for(int i = 1, id; i <= Qs; ++i) {
            int t = read(), opt = read();
            while(!Q2.empty() and Q2.top().tm <= t) {
                Node1 x = Q2.top();
                Q2.pop();
                if(vis[x.nid])
                    continue;
                Node pp;
                pp.id = x.id, pp.nid = x.nid, pp.tm = x.tm;
                Q1.push(pp);
                T.Add(x.id, 1);
            }

            if(opt == 0) {
                id = read();
                Q2.push(Node1(id, ++tot, a[id] + t));
                v[id].push_back(Node2(tot, a[id] + t));
            }

            if(opt == 1) {
                if(Q1.empty())
                    puts("Yazid is angry.");
                else {
                    Node x;
                    x.id = -1;
                    while(!Q1.empty()) {
                        x = Q1.top();
                        Q1.pop();
                        if(vis[x.nid])
                            continue;
                        break;
                    }
                    if(x.id == -1 or v[x.id].empty() or vis[x.nid])
                        puts("Yazid is angry.");
                    else {
                        T.Add(x.id, -1);
                        v[x.id].pop_front();
                        vis[x.nid] = true;
                        printf("%d\n", x.id);
                    }
                }
            }

            if(opt == 2) {
                id = read();
                if(v[id].empty())
                    puts("YJQQQAQ is angry.");
                else {
                    deque <Node2> :: iterator it = v[id].begin();
                    Node2 x = *it;
                    if(x.tm > t)
                        printf("%d\n", x.tm - t);
                    else {
                        vis[x.nid] = true;
                        T.Add(id, -1);
                        v[id].pop_front();
                        puts("Succeeded!");
                    }
                }
            }

            if(opt == 3) {
                int l = read(), r = read();
                printf("%d\n", T.Ask(r) - T.Ask(l - 1));
            }
        }
    }

    init();

    #ifndef ONLINE_JUDGE
        getchar();
    #endif
    return 0;
}