题解：P13744 [NWERC 2024] Flowing Fountain

PDAFX · 2025-10-24 21:08:41 · 题解

题目大意

有两种操作：

1. 往盆子里加啤酒，每一层啤酒会往容量更大的比它更低的层级流。

2. 查询盆子中啤酒数量。

令 a_x 表示目前啤酒容量。

首先使用单调栈，求出往下流的层级，然后建一个类似于链表的结构。

每一次添加啤酒时，顺着链表一层一层往下模拟倾倒，直到无法溢出为止，然后同时修改下层链表。

查询直接输出 a_x 即可。

时间复杂度 O(n)。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=3e5+5;
int n,q,u,v,top,a[N],c[N],nxt[N],stk[N];
char opt;
int update(int x,int y)
{
    if(!x)return 0;
    if(a[x]+y<c[x])return a[x]+=y,x;
    y+=a[x]-c[x],a[x]=c[x];
    return nxt[x]=update(nxt[x],y);
}
int main()
{
    freopen("flowing.in","r",stdin);
    freopen("flowing.out","w",stdout);
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)
    {
        cin>>c[i];
        while(top&&c[stk[top]]<c[i])nxt[stk[top--]]=i;
        stk[++top]=i;
    }
    while(q--)
    {
        cin>>opt>>u;
        if(opt=='+')
        {
            cin>>v;
            update(u,v);
        }
        else cout<<a[u]<<endl;
    }
    return 0;
}