D. Optimal Partition

考虑到动态规划有:$dp_i=max\{dp_i,dp_j+i-j\}$其中$(j < i,sum[j] \leqslant sum[i])$，所以我们可以用树状数组维护最大值$dp_i-i$

#include <algorithm>
#include <bitset>
#include <map>
#include <vector>
#include <string>
#include <iostream>
#include <cmath>
#include <stack>
#include <set>
/*
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
*/
using namespace std;

const double eps = 1e-10;
const double pi = 3.1415926535897932384626433832795;
const double eln = 2.718281828459045235360287471352;

#define f(i, a, b) for (int i = a; i <= b; i++)
#define LL long long
#define IN freopen("in.txt", "r", stdin)
#define OUT freopen("out.txt", "w", stdout)
#define scan(x) scanf("%d", &x)
#define mp make_pair
#define pb push_back
#define sqr(x) (x) * (x)
#define pr1(x) printf("Case %d: ",x)
#define pn1(x) printf("Case %d:\n",x)
#define pr2(x) printf("Case #%d: ",x)
#define pn2(x) printf("Case #%d:\n",x)
#define lowbit(x) (x&(-x))

#define fi first
#define se second
#define sz(x) int((x).size())
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define summ(a) (accumulate(all(a), 0ll))

typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;

const int max_n=500005, inf=10000000;
int t, n, a[max_n], dp[max_n], ord[max_n];
long long pref[max_n];


// Fenwick tree with prefix maximum

struct BIT
{
    int ff[(int)5e5+9];
    void build(){
        for(int i=1;i<=n;++i)ff[i]=-0x3f3f3f3f;
    }
    void add(int p,int v){
        while(p<=n)ff[p]=max(ff[p],v),p+=lowbit(p);
    }
    int query(int p){
        int res=-0x3f3f3f3f;
        while(p)res=max(res,ff[p]),p-=lowbit(p);
        return res;
    }
}b;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
   // IN;OUT;
    cin >> t;


    while (t--) {
        cin >> n;
        vector<pair<long long, int> > v;
        for (int i=1; i<=n; i++) {
            dp[i]=0;
            cin >> a[i];
            pref[i]=pref[i-1]+a[i];
            v.push_back({pref[i], -i});
        }
        sort(v.begin(), v.end());
        for (int i=0; i<n; i++) {
            ord[-v[i].second]=i+1;
        }
        // smaller prefix sum, smaller ord[i]
        // if j<i they have equal prefix sums, than ord[i]<ord[j], this way we cannot count [j+1, ... i] as a winning segment


        b.build();

        for (int i=1; i<=n; i++) {
            dp[i]=(dp[i-1]+(a[i]<0 ? -1 : a[i]>0 ? 1 : 0));
            // The last segment is 1 long.

            dp[i]=max(dp[i], b.query(ord[i])+i);
            //cerr<<ord[i]+i<<"__f-q\n";
            if (pref[i]>0) dp[i]=i;
            // Segment [1, ... i] is winning, so dp[i]=i;

            b.add(ord[i], dp[i]-i);
            //cerr<<ord[i]<<"::"<<dp[i]-i<<"__f-ad\n";
            //cerr<<"---------------------------\n";
        }
        cout << dp[n] << "\n";

    }
    return 0;
}


/*
 * ┌───┐┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐  ┌──┐  ┌──┐  ┌──┐
 * │╠╣1││Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  │┌┐│  │┌┐│  │┌┐│
 * ├───┤└───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └└┘┘  └└┘┘  └└┘┘
 * │╠╣2│┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
 * └───┘│~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
 * ┌───┐├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
 * │╠╣3││ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
 * ├───┤├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
 * │╠╣4││ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
 * └───┘├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
 * ┌───┐│ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
 * │╠╣5│├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
 * ├───┤│ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
 * │╠╣6│└─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
 * └───┘
 */