526互联

P4032 [Code+#2] 火锅盛宴

发布时间 2023-10-04 18:25:49作者: carp_oier

prologue

树状数组推荐写法，感谢巨佬樱雪喵的教学。


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

inline void add(int x, int c)
{
	for(; x <= n; x += lowbit(x)) tr[x] += c;
}

inline int sum(int x)
{
	int res = 0;
	for(; x; x -= lowbit(x)) res += tr[x];
	return res;
}

analysis

很弱的模拟题？

这个题目主要解决的问题就以下几个：

  1. 对于 YJQQQAQ 怎么快速的查询和删除它要吃掉的东西。
  2. 怎么维护东西熟了没熟（不干不净吃了没病？）
  3. 维护一个区间里面的和。

我们可以想到，关于时间类型的问题，它必定是顺着时间进行的（废话但是有用），不太可能出现时间倒流（某些图论题存下来离线，倒序处理除外）。那么我们就可以用时间这一维度来搞个优先队列，然后对于每一个新输入的时间，就来处理这个锅里面的东西是不是已经做好了。

我们又注意到，Yazid 这个人很喜欢吃编号小的食物，所以我们就可以选择用另外一个优先队列来存储这些已经做好的食物。

我们还要处理怎么解决 YJQQQAQ 的问题。我们可以给每种食物开一个结构体，里面存一个队列和一个 cnt。队列用来存还没有煮熟的吃的， cnt 用来存现在做好的还没有被吃了的食物有多少。

对于一个区间的和我们可以采用线段树或者树状数组。因为树状数组的时间、空间都要优于线段树。所以我就用树状数组实现了（主要是懒的敲线段树了。

剩下的就貌似是一个比较大的模拟题了。（

code time

（之前调上面树状数组那一块一直没调出来，然后压了点行。）

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rl register ll
#define wl putchar('\n')
#define ws putchar(' ')

template <class T>

inline void read(T &res)
{
    char ch; bool f = 0;
    while((ch = getchar()) < '0' || ch > '9') f |= ch == '-';
    res = ch ^ 48;
    while((ch = getchar()) <= '9' && ch >= '0') res = (res << 1) + (res << 3) + (ch ^ 48);
    res = f ? ~res + 1 : res;
}

inline void ww(ll x)
{
    if(x < 0) x = ~x + 1, putchar('-');
    if(x > 9) ww(x / 10);
    putchar(x % 10 ^ 48);
}


const ll N = 1e5 + 10;

ll n, m, eat[N], s[N], tr[N];

struct node
{
    ll id, time;
    bool operator <(const node &x) const 
    {
        return time > x.time;
    }
};

struct pot
{
    ll cnt;
    queue<ll> T;
    inline void clean()
    {
        cnt = 0;
        while(T.size()) T.pop();
    }
}pot[N];

priority_queue<node> q;
priority_queue<ll> ripe;

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

inline void add(ll x, ll c)
{
    for(; x <= n; x += lowbit(x)) tr[x] += c;
}

inline ll sum(ll x)
{
    ll res = 0;
    for(; x; x -= lowbit(x)) res += tr[x];
    return res;
}

int main()
{
    // freopen("1.in", "r", stdin), freopen("1.out", "w", stdout);

    ll T; read(T);
    while(T -- )
    {
        read(n);
        while(q.size()) q.pop(); while(ripe.size()) ripe.pop(); 
        for(rl i=1; i <= n; ++ i)
        {
            read(s[i]);
            eat[i] = 0;
            pot[i].clean();
            tr[i] = 0;
        }
        
        read(m);
        while(m -- )
        {
            ll t, op, a, b;
            read(t), read(op);

            while(q.size() && q.top().time <= t)
            {
                ll id = q.top().id;
                add(id, 1);

                pot[id].cnt ++ ; pot[id].T.pop();
                ripe.push(-id);

                q.pop();
            }

            if(op == 0) { read(a), q.push({a, t + s[a]}), pot[a].T.push(t + s[a]); }
            else if(op == 1)
            {   
                ll id = -1;
                while(ripe.size())
                {
                    ll x = -ripe.top();
                    ripe.pop();
                    if(eat[x] > 0) -- eat[x];
                    else 
                    {
                        id = x;
                        break; 
                    }
                }

                if(id == -1) puts("Yazid is angry.");
                else ww(id), add(id, -1), -- pot[id].cnt, wl;
            }
            else if(op == 2)
            {
                read(a);
                if(pot[a].cnt)
                {
                    -- pot[a].cnt; add(a, -1); ++ eat[a];
                    puts("Succeeded!");
                }
                else 
                {
                    if(pot[a].T.size()) ww(pot[a].T.front() - t), wl;
                    else puts("YJQQQAQ is angry.");
                }
            }
            else 
            {
                read(a), read(b);
                ww(sum(b) - sum(a - 1)), wl;
            }
        }
    }
    return 0;
}