解题思路

这题一共三个询问，我们可以先从最简单的第三个询问开始分析

第三个询问

我们可以用线段树（树状数组）来维护所有已经熟的食物，每次询问的时间复杂度为O（logn）

第一个询问

由于我们在做第三问时建立一颗线段树（树状数组），所以我们这里可以直接用线段树来解决这一问：
若整个区间的和为0，则没有食物。
若有食物，则：
用二分来找出有值但最小的点（左右端点相同的区间），该点就是所求的食物编号，每次询问的时间复杂度为O（（logn）^2），然后将该点减一,复杂度O(1)，所以，这步总的复杂度为O（（logn）^2）

第二个询问

我们给每一个食物建一个队列（因为同一种食物煮熟花的时间相同，所以越晚入队，煮熟的时间就越晚），每次询问时如果队列为空，则没有食物，如果队列最前面的元素小于当前时间，则成功，否则，则用队列最前面的元素减去当前时间，即为还需等待的时间，复杂度O(1)

一二问相互影响问题

由于拿走食物对一二问都有影响，所以我们在第一问删除时，要把用于第二问的队列元素出队，同样，在第二问删除时，要把用于第一三问的线段树更新，所以第二问的复杂度变为O(logn)

加入新的食物所需的操作

每次加入新的食物，我们将该食物煮熟的时间加入该食物的队列中，注意：不要更新线段树，只有食物煮熟时才更新线段树

在每一步之前的操作

根据现在的时间，把所有已经煮熟的食物加入对应的队列和线段树中

注意事项

注意清空数据，防止影响到下一组数据！！！

代码实现

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
#include<cstdio>
using namespace std;
int n;
const int mx=101010;
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
queue<int>food[mx];
int q_num;//询问总数 
int cost[mx];//每种食物需要的时间 
#define lowbit(i) i&-i
int tree[mx];
void change(int pos,int k){//pos位置+k 
    while(pos<=n){
        tree[pos]+=k;
        pos+=lowbit(pos);
    }
}
int query(int pos){//查询到pos为止有多少个食物 
    int ans=0;
    while(pos>=1){
        ans+=tree[pos];
        pos-=lowbit(pos);
    }
    return ans;
}
struct FOOD{//食物 
    int t;//煮熟时间 
    int pos;//食物编号
}; 
struct cmp1{
    bool operator () (const FOOD &a,const FOOD &b)const{
        return a.t>b.t;//按照结束时间从小到大排 
    }
};
priority_queue<FOOD,vector<FOOD>,cmp1>f1;//食物
void query_1(){//第一个问题：拿出编号最小的食物 
    if(!query(n)){//没有任何食物 
        printf("Yazid is angry.\n");
        return;
    }
    int l=1,r=n,mid=(l+r)>>1;
    while(l<r){
        if(query(mid)-query(l-1))r=mid;
        else l=mid+1;
        mid=(l+r)>>1;
    }
    printf("%d\n",mid);
    food[mid].pop();//食物出堆 
    change(mid,-1);
    return;
}
void query_2(int pos,int t){//第二问，pos食物是否有熟的，如果没有，最快熟的还要多久 
    if(food[pos].empty()){//没有该食物 
        printf("YJQQQAQ is angry.\n");
        return;
    }
    int tp=food[pos].front();
    if(tp<=t){//熟了 
        printf("Succeeded!\n");
        food[pos].pop();//从堆中删除该食物 
        change(pos,-1);//从树状数组中删除该食物 
        return;
    }
    else{
        printf("%d\n",tp-t);
        return;
    }
}
void query_3(int l,int r){//第三个问题：查询[l,r]之间有多少个食物 
    printf("%d\n",query(r)-query(l-1));
    return;
}
int main(){
    int T=Read();
    while(T--){
        q_num=0;
        n=Read();
        for(int i=1;i<=n;++i)cost[i]=Read();
        int num=Read();
        for(int i=1;i<=num;++i){
            int t=Read();
            int opt=Read();
            if(!f1.empty()){
                FOOD tp=f1.top();
                while(tp.t<=t){
                    f1.pop();
                    change(tp.pos,1);
                    if(f1.empty())break;
                    tp=f1.top();
                }
            }
            if(opt==0){
                int pos=Read();
                FOOD a;
                a.pos=pos;
                a.t=t+cost[pos];
                f1.push(a);
                food[pos].push(t+cost[pos]);
            }
            else if(opt==1){
                query_1();
            }
            else if(opt==2){
                int pos=Read();
                query_2(pos,t);
            }
            else{
                int l=Read(),r=Read();
                query_3(l,r);
            }
        }
        //清除数据，为下一组数据做准备 
        memset(tree,0,sizeof(tree));
        while(!f1.empty())f1.pop();
        for(int i=1;i<=n;i++)while(!food[i].empty())food[i].pop();//清空队列
    }
    return 0;
}

因为太懒所以用了优先队列和树状数组，你们可以用手写堆和线段树

火锅盛宴___题解