自动搬运

查看原文

来自洛谷，原作者为

	Areka6219 When you are young they assume you know nothing

搬运于2025-08-24 21:55:45，当前版本为作者最后更新于2021-08-10 17:11:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

• 我们把食物分为两个集合，熟的为 $S_1$，不熟为 $S_2$。
• $Add_0$​​：在集合 $S_2$​​ 中加入一个元素，此元素在经过 $t_{id}$​​ 时间后会自动加入 $S_1$​​，且在 $S_2$​​ 中消失。
• $Ask_1$：询问 $S_1$ 中元素的最小编号，若 $S_1 = \varnothing$ ，则输出 Yazid is angry.。
• $Ask_2$：询问某个特定编号的食物存在于 $S_1$ 中，若存在，输出 Succeeded! ，若不存在，则查询 $S_2$ 中是否存在该元素，若存在，输出该元素还需多长时间加入集合 $S_1$ 中，若 $S_2$ 中也不存在该元素，则输出 YJQQQAQ is angry.。
• $Ask_3$​：查询集合 $S_1$​ 中 $[l,r]$ 内共有多少元素。

分析

• 提供思路：树状数组+两个优先队列+一个双端队列（可能有点十分麻烦）。
• 首先针对 $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;
}