题解：P13744 [NWERC 2024] Flowing Fountain

czx35 · 2026-10-22 12:46:49 · 题解

题目传送门

思路

这是一道并查集的题，我们可以在开始时把一个数后第一个大于它的数看成它的父亲节点，在后面的操作中，如果父亲节点满了，就进行路径压缩，以此类推。

接下来就是开始时的预处理，因为要求这个数后第一个大于它的数，不难想到要使用单调栈优化，不清楚单调栈的请看这里。

时间复杂度

初始化：O(n)。

询问：O(q \log n)。

一共是 O(n+q \log n)。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,q,a[1000010],x,y,bb[1000010],cc;
char ch;
struct A{
    int xb,xx;//xb：当前香槟量，xx：它的父亲节点
}b[1000010];
int f(int d,int s){
    if(s>a[d]-b[d].xb){//香槟继续向下溢出
        s-=a[d]-b[d].xb;
        b[d].xb=a[d];
    }else{
        b[d].xb+=s;
        s=0;
        return d;
    }
    return b[d].xx=f(b[d].xx,s);//路径压缩
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)b[i].xx=n+1;//如果后面没有比他大的，都到第n+1个
    a[n+1]=1e18;//n+1（地板）容积无限
    for(int i=1;i<=n;i++){
        cin>>a[i];
        while(cc>0&&a[bb[cc]]<a[i]){//单调栈
            b[bb[cc]].xx=i;
            cc--;
        }
        bb[++cc]=i;
    }
    while(q--){
        cin>>ch;
        if(ch=='+'){
            cin>>x>>y;
            f(x,y);//并查集
        }else{
            cin>>x;
            cout<<b[x].xb<<'\n';//直接输出
        }
    }
    return 0;
}