补题： Potions (Hard Version)

这是问题的硬版本。唯一的区别是在这个版本中n≤200000。只有当问题的两个版本都得到解决时，您才能进行 hack。

一行中有 n 个药水，最左边是药水 1，最右边是药水 n。每种药水都会在喝醉时通过 ai 增加你的健康。 ai 可以是负数，这意味着药水会降低生命值。

你从 0 生命值开始，你会从左向右走，从第一个药水到最后一个。对于每种药水，您可以选择饮用或忽略它。您必须确保您的健康状况始终为非负值。

你最多可以喝多少药水？

输入
第一行包含一个整数 n (1≤n≤200000)——药水的数量。

下一行包含 n 个整数 a1, a2, … ,an (−109≤ai≤109)，代表饮用该药水后健康状况的变化。

输出
输出一个整数，你可以喝的最大药水数量，而你的健康不会变成负数。
笔记
对于样本，您可以通过服用药水 1、3、4、5 和 6 来喝 5 种药水。 不可能喝下所有 6 种药水，因为您的健康在某些时候会变成负值

对于这个问题一开始一直想的是将两个正数之间的区间分开讨论，之后再加上之后的区间，后来发现这种想法的实现和维护特别困难。
下面是正解：
对于每次需要喝的药水，只要喝不死，就往死里喝。
非常巧妙的使用到了升序的优先队列，这样就可以把喝过的药水中最小的放到最上边，一旦遇到再喝药水就会死掉的情况就用之后要喝的药水和队头药水进行比较，如果喝这瓶药水更优的话就进行替换，在这个过程中的最大值就是结果最大值

~~~c++

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define buff  ios::sync_with_stdio(false);
#define Gint_queue priority_queue<int,vector<int>,greater<int> >
#define Gll_queue priority_queue<ll,vector<ll>,greater<ll> >
#define gcd __gcd
#define debug printf("***\n")
#include<stdio.h>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
#include<numeric>
#include<math.h>
#include<list>
#include<bitset>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define int long long
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int maxn=2e5+7;
int a[maxn];
signed main()
//int main()
{
    int n;
    scanf("%lld",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%lld",&a[i]);
    }
    int hp=0,cnt=0,ans=0;
    Gll_queue Q;
    for(int i=0;i<n;i++)
    {
        if(hp+a[i]>=0)
        {
            if(a[i]<0)
            {
                Q.push(a[i]);
            }
            hp+=a[i];
            cnt++;
            ans=max(ans,cnt);
        }else{
            if(Q.empty())continue;
            if(Q.top()<a[i])
            {
                hp-=Q.top();
                hp+=a[i];
                Q.pop();    
                Q.push(a[i]);
            }
        }
    }
    printf("%lld",ans);
}