B3799 [NICA #1] 序列

[B3799 NICA #1] 序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

发现两个操作跟顺序无关，最大子序列和就是所有正数之和。

对数组进行排序，之后求前缀和。用$now$记录操作一加了多少。找到第一个$a_i+now<0$的位置，求${\sum }_k^{i}a[k]$即可。

如何快速求$i$下标，可以用二分。

代码如下：

(自写二分)

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 21;
using LL = long long;
LL pre[N], a[N];
int main()
{
    int n,q; cin>>n>>q;
    for(int i = 1; i <= n; ++i) cin>>a[i];
    sort(a + 1, a + n + 1, greater<int>());
    for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
    LL now = 0;
    while(q--) {
        int op,k; cin>>op;
        if(op == 1) cin>>k, now += k;
        else {
            auto check = [&](int mid) -> bool {
                return a[mid] + now > 0;
            };
            int l = 1, r = n;
            while(l < r) {
                int mid = l + r + 1 >> 1;
                if(check(mid)) l = mid;
                else r = mid - 1;
            }
            LL ans = pre[l] + now * l;
            if(a[l] + now < 0) ans = 0;
            cout<<ans<<endl;
        }
    }
}

（用upper_bound）

upper_bound函数用法：

如果是stl容器，则找到返回的是迭代器下标，否则返回v.end()。

如果是普通数组，找到返回数组下标，否则返回0。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 21;
using LL = long long;
LL pre[N], a[N];
int main()
{
    int n,q; cin>>n>>q;
    for(int i = 1; i <= n; ++i) cin>>a[i];
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i) pre[i] = pre[i - 1] + a[i];
    LL now = 0;
    while(q--) {
        int op,k; cin>>op;
        if(op == 1) cin>>k, now += k;
        else {
            LL pos = upper_bound(a + 1, a + n + 1, -now) - a - 1;
            LL sum = pre[n] - pre[pos] + now * (n - pos);
            cout<<sum<<endl;
        }
    }
}