把过去和现在的笔记记录也搬了过来，也算是给以后留个念想吧，想想一开始打acm就是图一乐，后来发现这游戏还挺上头的，也算是度过了一段电竞生涯（xs）
早些时候的笔记写的好中二，连我自己看着都羞耻。
不过，就喜欢这种羞耻的感觉。
收录的题目大部分是个人认为质量不错的题目，以DP为主，非DP的题目都用※进行了标识。
当然，有些题解思路本身也是源自其他人的，不过除非特殊标注，否则都是用的自己的代码。

题目大意：

CF 1668D Optimal Partition
题目大意：一个数组(5e5)，其中每个子段的价值为：当子段和为正则为子段长度，为负则为子段长度的相反数，为0则为0。现将其划分为任意个子段，需要求得价值的最大值并输出最大价值。

解：

一眼dp，转移依靠区间，5e5的复杂度不允许去枚举区间的割点，于是想到分离参数去单调队列，但是由于区间的转移是和转移的子段正负有关的，很难去直接用单调队列分离。
题目需要进一步的结论，事实上通过贪心我们知道，如果全是正数那么怎么分都可以，而如果有负数的话，我们尽量用正数把它拉上来使其价值从-1变为1，但是如果实在没法拉上来的负数，我们更加倾向于让他单独一个划分，使其造成的影响最小，避免其将原本的正数拉成负数。
所以在进行区间转移的时候，我们只需要考虑正区间的转移，也就是dp[i]=dp[k]+val(k+1,i)时，sum(k+1,i)一定为正，而另一种转移则是直接dp[i]=dp[i-1]+a[i]/abs(a[i])，考虑负数的情况。
但是即便如此，我们依然不知道对于i来说，哪些k能够进行转移，这时候用到权值线段树解决这个问题。
将原数组的前缀和求出，并按照前缀和去从小到大排序，记录下每一个数在前缀和序中的位置，这样很容易发现，在前缀和序中排在后面的减去前面的（并且原本在数组中就出现在前面的）肯定区间和大于0，那么对于每个数，我只要维护比它位置更小的数里面分参后最大的数，这个过程可以通过权值线段树实现。
各种意义上非常nb的题目，前后用到了贪心、单调队列dp、权值线段树、前缀和相减的思想，实在是2100之鉴。

代码

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#include <istream>
#include <map>
#include <cmath>
#include <stack>
#include <set>
#include <cstring>
#include <string>
#include <fstream>
#define ll long long
#define maxn 500005
#define mdl 998244353
#define clr(a,n) for(int i=0;i<n;i++)a[i]=0
#define cfast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pll pair<ll,ll>
#define pii pair<int,int>
#define inc(i,a,n) for(int i=a;i<n;i++)
#define vset(a,n,m) for(ll i=0;i<n;i++)a[i]=m;
#define endl '\n'
using namespace std;
ll n,tree[maxn],a[maxn],qzh[maxn],pos[maxn],dp[maxn];
struct cpr {
    ll qzh, pos;
    friend bool operator<(cpr c1, cpr c2) {
        if (c1.qzh == c2.qzh)return c1.pos > c2.pos;
        return c1.qzh < c2.qzh;
    }
}cp[maxn];
ll lowbit(ll num) {
    return num & -num;
}
void add(ll s, ll num) {
    for (ll i = s; i <= n+2; i += lowbit(i)) tree[i]=max(tree[i],num);
}
ll ask(ll s) {
    ll ans = -1e18;
    for (ll i = s; i >= 1; i -= lowbit(i)) ans=max(ans,tree[i]);
    return ans;
}
int main() {
    cfast;
    int t;
    cin >> t;
    while (t--) {
        cin >> n;
        inc(i, 1, n + 2)tree[i] = -1e18;
        qzh[1]=a[1] = 0;
        inc(i, 2, n+2) {
            cin >> a[i];
            qzh[i] = qzh[i - 1] + a[i];
            cp[i].qzh = qzh[i];
            cp[i].pos = i;
        }
        cp[1].qzh = 0;
        cp[1].pos = 1;
        sort(cp+1, cp + n + 2);
        inc(i, 1, n + 2) {
            pos[cp[i].pos] = i;
        }
        inc(i, 1, n + 2) {
            dp[i] = dp[i - 1] + a[i] / max(1ll, abs(a[i]));
            ll tmp = ask(pos[i]);
           // cout << "tmp=" << tmp << endl;
            dp[i] = max(dp[i], tmp + i);
            add(pos[i], dp[i] - i);
        }
        cout << dp[n+1] << endl;
    }
}
/*



*/