【题解】[Code+#2] 火锅盛宴 线段树+优先队列 LuoGuP4032 ——first_fan

此题可以 $\Large\text{线段树+优先队列}$解决。

首先看第一问，我们考虑开三个优先队列：

• $\sf {q1[i]}$，用于存储食物 $\sf i$的成熟时间

• $\sf {q2[i]}$，用于存储成熟时间小于 $\sf i$的食物

• 对每个食物开一个 $\sf {e[i]}$，用于存储其成熟时间

接下来把线段树编号为 i 的位置自增 1 就好。

第二问，按照编号最小的顺序找成熟食品，这时候取出 $\sf {q2[i]}$使用即可，修改更新线段树。

第三问，查找指定编号食物，直接查找 $\sf {e[i]}$，不成熟输出距离成熟的时间，即 $\sf \text{e[i]-当前时间}$。

第四问，查询区间内成熟食物个数，用线段树统计即可，上面每次取出操作时已经更新过，直接找就行了。

上代码 (附注释)

#include<bits/stdc++.h>
#define ll long long
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
using namespace std;
int read()
{
    int num=0;
    int flg=1;
    char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
        {
            flg=-1;
        }
        c=getchar();
    }
    while(isdigit(c))
    {
        num=(num<<1)+(num<<3)+(c^48);
        c=getchar();
    }
    return num*flg;
}
int seg[400002];//线段树
int n,qst;//食材个数，询问次数
int s[100005];//食材成熟所需时间
int rest[100005];

priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q1;
priority_queue<int,vector<int>,greater<int> >q2,e[100005];
//q1,q2,e
void modify(int nd,int l,int r,int x,int y)
{
    seg[nd]+=y;
    if(l==r)
    {
        return;
    }
    int mid=(l+r)>>1;
    if(x<=mid)
    {
        modify(ls(nd),l,mid,x,y);
    }
    else
    {
        modify(rs(nd),mid+1,r,x,y);
    }
}//线段树修改
int query(int nd,int l,int r,int x,int y)
{
    if(l==x&&r==y)
    {
        return seg[nd];
    }
    int mid=(l+r)>>1;
    if(y<=mid)
    {
        return query(ls(nd),l,mid,x,y);
    }
    else if(x>mid)
    {
        return query(rs(nd),mid+1,r,x,y);
    }
    else
    {
        return query(ls(nd),l,mid,x,mid)+query(rs(nd),mid+1,r,mid+1,y);
    }
}//线段树求和
void solve()
{
    n=read();
    for (int i=1; i<=n; i++)
    {
        s[i]=read();
    }
    for (int i=1; i<=n; i++)
    {
        rest[i]=0;
    }
    for (int i=1; i<=400001; i++)
    {
        seg[i]=0;
    }
    while (!q1.empty())
    {
        q1.pop();
    }
    while (!q2.empty())
    {
        q2.pop();
    }
    for (int i=1; i<=n; i++)
    {
        while (!e[i].empty())
        {
            e[i].pop();
        }
    }//龟速清空
    qst=read();
    while (qst--)
    {
        int tim=read(),op=read();
        while (!q1.empty()&&q1.top().first<=tim)
        {
            q2.push(q1.top().second);
            modify(1,1,n,q1.top().second,1);
            q1.pop();
        }
        if(op==0)
        {
            int u=read();
            q1.push(make_pair(tim+s[u],u));
            e[u].push(tim+s[u]);
        }//问 1
        else if(op==1)
        {
            while (!q2.empty()&&rest[q2.top()])
            {
                rest[q2.top()]--;
                q2.pop();
            }
            if(q2.empty())
            {
                printf("Yazid is angry.\n");
            }
            else
            {
                printf("%d\n",q2.top());
                modify(1,1,n,q2.top(),-1);
                e[q2.top()].pop();
                q2.pop();
            }
        }//问 2
        else if(op==2)
        {
            int u=read();
            if(e[u].empty())
            {
                printf("YJQQQAQ is angry.\n");
            }
            else
            {
                if(e[u].top()<=tim)
                {
                    printf("Succeeded!\n");
                    modify(1,1,n,u,-1);
                    rest[u]++;
                    e[u].pop();
                }
                else
                {
                    printf("%d\n",e[u].top()-tim);
                }
            }
        }//问 3
        else
        {
            int l=read();
            int r=read();
            printf("%d\n",query(1,1,n,l,r));
        }//问 4
    }
}
int main()
{
    int first_fan=read();
    while (first_fan--)
    {
        solve();//多组数据
    }
}

还有一件事：这题时间卡得松，空间卡得紧，所以开数组不要太豪迈了……