HDU多校第三场 1004 Distribution of books —— 离散化建权值线段树

题目链接：点我啊╭(╯^╰)╮

题目大意：

    $n$ 本书，$k$ 个学生，每本书的权值可能为负
    每个学生的快乐为他所获得的书的权值和
    每个学生获得的书的编号必须是连续的
    分书也必须按学生的编号顺序，最后可以剩下书
    问最后所有学生最大的快乐值最小为多少？？

解题思路：

    二分快乐值 $x$，则问 $n$ 个人能否在满足 $x$ 的前提下分成 $k$ 组
    $dp[i]$ 为到第 $i$ 个人最多可以分的组数，$pre$ 为前缀
    $dp[i]=max(dp[j])+1$     $pre[i]?pre[j]\le x$
    这是个 $n^2$ 的 $dp$，发现可以用数据结构优化

    先离散化 $pre[i]$，然后按照离散化后的 $pre$ 数组建权值线段树
    枚举 $i$，要找到 $pre[j]\ge pre[i]?x$ 的最大的 $dp[j]$
    则只需要在权值线段树里找 $（pre[i]?x，max）$ 里的最大值即可
    时间复杂度：$O(nlo{g}^{2}n)$

核心：用离散化后的值建权值线段树

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 10;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
int T, n, k, cnt;
ll pre[maxn], ls[maxn];
int t[maxn<<2], a[maxn], id[maxn];void build(int l,int r,int rt){if(l==r){t[rt] = 0;return ;}int m = l + r >> 1;build(lson);build(rson);t[rt] = max(t[rt<<1], t[rt<<1|1]);
}void update(int pos,int c,int l,int r,int rt){if(l==r){t[rt] = max(c, t[rt]);return;}int m = l + r >> 1;if(pos<=m) update(pos,c,lson);else update(pos,c,rson);t[rt] = max(t[rt<<1], t[rt<<1|1]);
}int query(int L,int R,int l,int r,int rt){if(L<=l && r<=R) return t[rt];int m = l + r >> 1;int ret = -1e9;if(L<=m) ret = max(ret, query(L,R,lson));if(R>m) ret = max(ret, query(L,R,rson));return ret;
}bool check(ll m){build(1,n,1);for(int i=1; i<=n; i++){int p = lower_bound(ls+1, ls+cnt+1, pre[i]-m) - ls;int q = query(p,n,1,n,1);if(q) update(id[i],q+1,1,n,1);else if(pre[i]<=m) update(id[i],1,1,n,1);}return query(1,n,1,n,1)>=k;
}int main() {scanf("%d", &T);while(T--){scanf("%d%d", &n, &k);for(int i=1; i<=n; i++){scanf("%d", a+i);ls[i] = pre[i] = pre[i-1] + a[i];}sort(ls+1, ls+n+1);cnt = unique(ls+1, ls+n+1) - ls - 1;for(int i=1; i<=n; i++)id[i] = lower_bound(ls+1, ls+cnt+1, pre[i]) - ls;ll l = -1e15, r = 1e15;while(l<=r){ll mid = l + r >> 1;if(check(mid)) r = mid - 1;else l = mid + 1;}printf("%lld\n", l);}
}