E. Sum Over Zero

搞半天是数组开小了…

#include<bits/stdc++.h>
using namespace std;
 
using ll=long long;
int P;
 
// assume -P <= x < 2P
int norm(int x) {
    if (x < 0) {
        x += P;
    }
    if (x >= P) {
        x -= P;
    }
    return x;
}
template<class T>
T power(T a, ll b) {
    T res = 1;
    for (; b; b /= 2, a *= a) {
        if (b % 2) {
            res *= a;
        }
    }
    return res;
}
struct Z {
    int x;
    Z(int x = 0) : x(norm(x)) {}
    Z(ll x) : x(norm(x % P)) {}
    int val() const {
        return x;
    }
    Z operator-() const {
        return Z(norm(P - x));
    }
    Z inv() const {
        assert(x != 0);
        return power(*this, P - 2);
    }
    Z &operator*=(const Z &rhs) {
        x = ll(x) * rhs.x % P;
        return *this;
    }
    Z &operator+=(const Z &rhs) {
        x = norm(x + rhs.x);
        return *this;
    }
    Z &operator-=(const Z &rhs) {
        x = norm(x - rhs.x);
        return *this;
    }
    Z &operator/=(const Z &rhs) {
        return *this *= rhs.inv();
    }
    friend Z operator*(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res *= rhs;
        return res;
    }
    friend Z operator+(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res += rhs;
        return res;
    }
    friend Z operator-(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res -= rhs;
        return res;
    }
    friend Z operator/(const Z &lhs, const Z &rhs) {
        Z res = lhs;
        res /= rhs;
        return res;
    }
    friend std::istream &operator>>(std::istream &is, Z &a) {
        ll v;
        is >> v;
        a = Z(v);
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const Z &a) {
        return os << a.val();
    }
};
 
template < typename T, auto op, auto e, typename F, auto mapping, auto composition,
           auto e1 >
class segtree
{
    int n;
    vector< T > v;
    vector< F > lazy;
    void build(int now, int l, int r, T a[])
    {
        if(l == r)
        {
            v[now] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(now * 2, l, mid, a);
        build(now * 2 + 1, mid + 1, r, a);
        v[now] = op(v[now * 2], v[now * 2 + 1]);
    }
    void pushup(int k) { v[k] = op(v[k * 2], v[k * 2 + 1]); }
    void pushdown(int k, int l, int r)
    {
        v[k] = mapping(v[k], lazy[k], l, r);
        if (l != r) {
            lazy[k * 2] = composition(lazy[k * 2], lazy[k]);
            lazy[k * 2 + 1] = composition(lazy[k * 2 + 1], lazy[k]);
        }
        lazy[k] = e1();
    }
 
    void modify(int now, int ql, int qr, int l, int r, F x)
    {
        pushdown(now, l, r);
        if (l > qr || r < ql) return;
        if (l >= ql && r <= qr) {
            lazy[now] = x;
            pushdown(now, l, r);
            return;
        }
        modify(now * 2, ql, qr, l, (l + r) / 2, x);
        modify(now * 2 + 1, ql, qr, (l + r) / 2 + 1, r, x);
        pushup(now);
    }
    T query(int now, int ql, int qr, int l, int r)
    {
        pushdown(now, l, r);
        if (l > qr || r < ql) return e();
        if (l >= ql && r <= qr) return v[now];
        return op(query(now * 2, ql, qr, l, (l + r) / 2),
                  query(now * 2 + 1, ql, qr, (l + r) / 2 + 1, r));
    }
 
public:
	segtree(T a[], int n) : segtree(n)
    {
        build(1, 1, n, a);
    }
    segtree(int n)
    {
        this->n = n;
        v = vector< T >(n << 2, e());
        lazy = vector< F >(n << 2, e1());
    }
 
    void modify(int l, int r, F x) { modify(1, l, r, 1, n, x); }
    T query(int l, int r) { return query(1, l, r, 1, n); }
};
 
template<typename T>
T MAX(T x, T y) {if(x > y) return x; else return y;}
template<typename T>
T MIN(T x, T y) {if(x < y) return x; else return y;}
template<typename T>
T PLUS(T x, T y) {return x + y;}
template<typename T,typename D>
T LAZY(T x,T lazy,D l,D r){return x + (r - l + 1) * lazy;}
 
/*  Note:
	typename T, auto op, T e, 
	typename F, auto mapping, auto composition,
	F e1
*/
 
struct F{
    Z mul;
    Z add;
};
 
using segtree_add=segtree< ll, PLUS<ll>, [](){return 0ll;}, ll,[](ll x, ll lazy, int l, int r) { return x + (r - l + 1) * lazy; }, PLUS<ll>, [](){return 0ll;} >;
using segtree_min=segtree< ll, MIN<ll>, [](){return 1e18;}, ll,[](ll x, ll lazy, int l, int r) { return x+lazy; },PLUS<ll>, [](){return 0ll;} >;
using segtree_max=segtree< ll, MAX<ll>, [](){return -1e18;}, ll,[](ll x, ll lazy, int l, int r) { return x+lazy; },PLUS<ll>, [](){return 0ll;} >;
using segtree_add_mul=segtree< Z, [](Z x, Z y) { return x + y; }, [](){return Z(0);}, 
     F, [](Z x, F t, int l, int r) { return x * t.mul + (r - l + 1) * t.add; },
     [](F t1, F t2)->F { return {(t1.mul * t2.mul), (t1.add * t2.mul + t2.add)}; }, 
     []()->F{return {1, 0};} >;
 
ll n,dp[(int)2e5+9],a[(int)2e5+9],b[(int)2e5+9],len;
 
int id(ll x){
	return lower_bound(b+1,b+1+len,x)-b;
}
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i],a[i]+=a[i-1];
	memcpy(b,a,sizeof(a));
	sort(b+1,b+2+n);
	len=unique(b+1,b+2+n)-b-1;
	segtree_max seg(len+1000);
	seg.modify(id(0),id(0),-seg.query(id(0),id(0)));
	for(int i=1,x;i<=n;++i){
		x=id(a[i]);
		dp[i]=seg.query(1,x)+i;
		dp[i]=max(dp[i],dp[i-1]);
		ll qsb=seg.query(x,x);
		if(qsb<dp[i]-i){
			seg.modify(x,x,dp[i]-i-qsb);
		}
	}
	cout<<dp[n];
}