记这个题主要是弥补一下数据结构优化DP的相关知识。题目来源：2019多校赛第三场D题。

题目描述

        zz6d likes reading very much, so he bought a lot of books. One day, zz6d brought n books to a classroom in school. The books of zz6d is so popular that K students in the classroom want to borrow his books to read. Every book of zz6d has a number i (1<=i<=n). Every student in the classroom wants to get a continuous number books. Every book has a pleasure value, which can be 0 or even negative (causing discomfort). Now zz6d needs to distribute these books to K students. The pleasure value of each student is defined as the sum of the pleasure values of all the books he obtains.Zz6d didn’t want his classmates to be too happy, so he wanted to minimize the maximum pleasure of the K classmates. zz6d can hide some last numbered books and not distribute them,which means he can just split the first x books into k parts and ignore the rest books, every part is consecutive and no two parts intersect with each other.However,every classmate must get at least one book.Now he wonders how small can the maximum pleasure of the K classmates be.

输入格式

        Input contains multiple test cases.
        The first line of the input is a single integer T which is the number of test cases. T test cases follow.
For each test case, the first line contains two integer n,k: the number of books and the number of his classmates. The second line contains n integers $a_1 ,a_2,…, a_{n−1},a_n.$ (aimeans the pleasure value of book i.)$\sum n<=2*10^5.$

输出格式

        For each case, print the smallest maximum pleasure of the K classmates, and one line one case.

输入输出样例

Sample input

2
4 2
3 -2 4 -2
5 4
-1 -1 -1 -1 6

Sample output

2
-1

题解

        一开始以为是个傻X二分+贪心（历史总是惊人地相似），交了很多发都WA，后来遇到hack数据：3 2 1 -3 2。
        首先二分答案是肯定的，问题关键在于如何判定答案正确性。既然贪心不对，考虑DP。令$dp(i)$表示前$i$本书在每一段和不超过$x$（二分出来的答案）的条件下，最多分几组。状态转移方程很容易列：

        这里的$sum(x,y)$表示闭区间$[x,y]$的和，可以用前缀和求。
        当无法分割时（或者总有部分剩余时），DP值就是负无穷大，最后在这些DP值中取一个最大的值，如果其不小于k，则答案可行。
        容易发现，DP复杂度是$O(n^2)$的，再加上二分的复杂度，总复杂度达到$O(n^2logn)$，肯定会T。
        DP数组可以看成一个函数，现在其实就是求一个最值，只不过对最值对应的前缀和有要求。不妨以前缀和为指标建立平衡树，用平衡树维护这些前缀和对应的DP值，使查询最值的复杂度降至$O(logn)$，这样总复杂度为$O(nlog^2n)$，就可以成功地AC了。

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
84
85
86
87
88
89
90
91
92
#include <bits/stdc++.h>

using namespace std;

inline int read() {
    char e = getchar();
    int s = 0, g = 0;
    while (e < '-')e = getchar();
    if (e == '-')g = 1, e = getchar();
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return g ? -s : s;
}

struct Node {
    int l, r, k, max, ss;
    long long v;
} nd[200005];
int op[200005], cnt = 1, root;
long long n, m, sum[200005], dp2[200005], dp1[200005], maxn, minn;

inline void update(int x) {
    nd[x].max = max(nd[x].ss, max(nd[nd[x].l].max, nd[nd[x].r].max));
}

void split(int rt, int &a, int &b, long long v) {
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (nd[rt].v <= v)a = rt, split(nd[rt].r, nd[a].r, b, v);
    else b = rt, split(nd[rt].l, a, nd[b].l, v);
    update(rt);
}

void merge(int &rt, int a, int b) {
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (nd[a].k < nd[b].k)rt = b, merge(nd[rt].l, a, nd[b].l);
    else rt = a, merge(nd[rt].r, nd[a].r, b);
    update(rt);
}

inline int newNode(long long s, int dp) {
    nd[cnt].l = nd[cnt].r = 0;
    nd[cnt].ss = dp, nd[cnt].v = s, nd[cnt].max = dp, nd[cnt].k = rand();
    return cnt++;
}

inline bool check(long long x) {//判定过程
    cnt = 1, root = 0;
    int ans = 0;
    if (op[1] <= x)merge(root, root, newNode(sum[1], 1)), ans = 1;
    else merge(root, root, newNode(sum[1], -100000000)), ans = -100000000;
    for (int i = 2; i <= n; i++) {
        int a, b, dp;
        split(root, a, b, sum[i] - x - 1), dp = nd[b].max + 1;
        if (sum[i] <= x)dp = max(1, dp);
        merge(root, a, b);
        split(root, a, b, sum[i]), merge(a, a, newNode(sum[i], dp)), merge(root, a, b);
        ans = max(ans, dp);
    }
    return ans >= m;
}

int main() {
    long long t = read();
    while (t--) {
        n = read(), m = read();
        for (int i = 1; i <= n; i++)op[i] = read();
        sum[1] = op[1], nd[0].max = -100000000;
        for (int i = 2; i <= n; i++)sum[i] = sum[i - 1] + op[i];
        dp2[1] = dp1[1] = op[1], maxn = op[1], minn = op[1];
        for (int i = 2; i <= n; i++) {
            dp1[i] = dp1[i - 1] < 0 ? op[i] : dp1[i - 1] + op[i];//求最大字段和和最小字段和，作为答案区间
            dp2[i] = dp2[i - 1] > 0 ? op[i] : dp2[i - 1] + op[i];
            maxn = max(maxn, dp1[i]), minn = min(minn, dp2[i]);
        }
        long long l = minn - 1, r = maxn, mid;
        while (l < r) {//(,]//二分答案过程
            if (r == l + 1) {
                printf("%lld\n", r);
                break;
            }
            mid = (l + r) / 2;
            if (check(mid))r = mid;
            else l = mid;
        }
    }
    return 0;
}