二分答案 + 平衡树 + dp

很显然的一道二分答案题，我们每次二分每组最大和，用dp来检测。

dp[i]表示前i本书能够分成的最多组数。

可以得到状态转移方程 dp[i] = max(dp[j]) + 1 (sum[i] - sum[j] <= mid) sum为前缀和。

显然这样是n^2的，考虑优化。

可以建一颗平衡树，每个节点存前缀和，dp值，已经子树里最大的dp值。

我们要找之前最大的dp值，又要满足前缀的的限制，将式子转换一下得到 sum[j] >= sum[i] - mid

我们可以在按sum值维护平衡树，找到sum[i] - mid的后继节点，这样要找的dp值的下标就在该节点以及该节点的右子树里。

再让每个节点维护它的子树的最大dp值，这样可以迅速的找到答案，只要直接返回该节点的dp值与它的子树的最大dp值中的最大值即可。

这点在插入节点的时候用pushup就可以实现拉。

我这里用的是splay，找起来很方便，直接把后继splay到根就好了。

#include 
    
     #define INF 233333333333333333#define full(a, b) memset(a, b, sizeof a)#define FastIn ios::sync_with_stdio(false), cin.tie(0)#define pb push_backusing namespace std;typedef long long LL;inline int lowbit(int x){ return x & (-x); }inline int read(){    int ret = 0, w = 0; char ch = 0;    while(!isdigit(ch)){        w |= ch == '-', ch = getchar();    }    while(isdigit(ch)){        ret = (ret << 3) + (ret << 1) + (ch ^ 48);        ch = getchar();    }    return w ? -ret : ret;}inline int lcm(int a, int b){ return a / __gcd(a, b) * b; }template 
     
      inline A fpow(A x, B p, C lyd){    A ans = 1;    for(; p; p >>= 1, x = 1LL * x * x % lyd)if(p & 1)ans = 1LL * x * ans % lyd;    return ans;}const int N = 300005;int _, n, k, a[N], tot, ch[N][2], mxid[N], id[N], fa[N], root, dp[N];LL pre[N], lower, upper, val[N];void go(){    root = 0, tot = 0;}inline int build(LL v, int i, int f){    ++ tot;    val[tot] = v, mxid[tot] = id[tot] = i;    fa[tot] = f, ch[tot][0] = ch[tot][1] = 0;    return tot;}inline void push_up(int rt){    mxid[rt] = id[rt];    if(ch[rt][0]) mxid[rt] = max(mxid[rt], mxid[ch[rt][0]]);    if(ch[rt][1]) mxid[rt] = max(mxid[rt], mxid[ch[rt][1]]);}inline void rotate(int x){    int y = fa[x], z = fa[y], p = (ch[y][1] == x) ^ 1;    ch[y][p ^ 1] = ch[x][p], fa[ch[x][p]] = y;    ch[z][ch[z][1] == y] = x, fa[x] = z;    ch[x][p] = y, fa[y] = x;    push_up(y), push_up(x);}inline void splay(int x, int goal){    while(fa[x] != goal){        int y = fa[x], z = fa[y];        if(z != fa[y]){            (ch[y][0] == x) ^ (ch[z][0] == y) ? rotate(x) : rotate(y);        }        rotate(x);    }    push_up(x);    if(goal == 0) root = x;}inline void insert(LL x, int i){    if(!root){        root = build(x, i, 0);        return;    }    int cur = root;    while(ch[cur][x > val[cur]]){        if(val[cur] == x) break;        cur = ch[cur][x > val[cur]];    }    if(val[cur] == x) id[cur] = max(id[cur], i), splay(cur, 0);    else ch[cur][x > val[cur]] = build(x, i, cur), splay(ch[cur][x > val[cur]], 0);}inline void find(LL x){    int cur = root;    while(ch[cur][x > val[cur]] && val[cur] != x)        cur = ch[cur][x > val[cur]];    splay(cur, 0);}inline int successor(LL x){    find(x);    if(val[root] >= x) return root;    int cur = ch[root][1];    while(ch[cur][0]) cur = ch[cur][0];    return cur;}inline int solve(LL x){    splay(successor(x), 0);    return max(id[root], mxid[ch[root][1]]);}inline bool calc(LL mid){    go();    insert(INF, 0);    for(int i = 1; i <= n; i ++){        int tmp = solve(pre[i] - mid);        if(tmp == 0 && pre[i] > mid) continue;        dp[i] = tmp + 1;        if(dp[i] >= k) return true;        insert(pre[i], dp[i]);    }    return false;}int main(){    //freopen("data.txt", "r", stdin);    for(_ = read(); _; _ --){        n = read(), k = read();        for(int i = 1; i <= n; i ++){            a[i] = read();            if(a[i] < 0) lower += a[i];            else upper += a[i];            pre[i] = pre[i - 1] + a[i];        }        LL l = lower, r = upper;        while(l < r){            LL mid = (l + r) >> 1;            if(calc(mid)) r = mid;            else l = mid + 1;        }        cout << l << endl;    }    return 0;}