T1 填数游戏

10%

爆搜答案即可。

另外30%

意味着每个数都要填到格子里，那么有一个很直观的贪心想法，大的数匹配大的数，小的数匹配小的数就可以使答案最大了。

50%

主要要意是鼓励选手思考比较简单的 $O(n^2)$ 做法。可以做 $O(n^2)$ 的前缀 max 优化 dp 做法。可以拿到 50 分。

100%

考虑另外 30% 的贪心。但是因为有一些数可以不选的，所以可以把数分为大于 0 和小于 0 的。

首先肯定是负数和负数匹配，正数和正数匹配。然后余下的数按照大的和大的匹配，小的和小的匹配的原则匹配即可。

复杂度 $O(N)$ ，注意开 longlong。

T2 摆渡车

权值线段树。

显然会选取 $1 \sim i-1$ 中数字最小的若干个数字，若对每个 $i$ 都对 $1 \sim i-1$ 重新排序，或者使用插入排序后再统计答案，期望得分为 30 分。

但注意到第 4 第 5 个数据点 M 小于等于 100，所以我们使用插入排序时可以只维护前 100 个数字（若存在 $a[i]=0$ 的特殊处理）的排序后的结果就好，期望得分 50 分。

满分做法可以使用权值线段树，线段树上每个结点维护对应权值区间范围内有多少个数字以及这些数字的和是多少，查询时每次判断左子树对应区间范围内有多少数字，相加后的和是否超过限制，超过则向左递归否则向有递归。时间复杂度 $O(Nlog_N)$ ，期望得分 100 分。

T3 分糖果

做法：二分+DP+离散化+树状数组

要求最大的最小，第一时间想到二分。关键在于二分答案 $mid$ 后怎么判断。

当 $K=1$ 时，显然只需要看一下是否存在某个前缀和小于等于 $mid$ 即可。期望得分 20 分。

当 $K \neq 1$ 时，我们可以使用 DP 来解决。用 $f[i]$ 表示前 $i$ 个数字中，最多可以分成多少段，使得每一段的和都小于等于 $mid$ 。若存在 $f[i]>=K$ ，则 $mid$ 是可行解，往小的范围继续二分，否则 $mid$ 不合法，往大的范围继续二分。转移方程如下：

$f[i] = max(f[j] 1)$ , 其中 $S[i]-S[j]<=mid$ ， $S$ 数组为数列 $a$ 的前缀和数组，正确性显然。时间复杂度为 $O(logRange*N^2)$ ，结合 $K=1$ 的情况，期望得分 50 分。

我们发现上面这个 DP 很慢，而且主要是状态转移太慢了，我们来思考如何优化状态转移。当 $S[i]$ 和 $mid$ 固定时，符合条件的 $j$ 就是那些满足 $S[j]>=S[i]-mid$ 的 $j$ ，而转移时就是在这些符合条件的 $j$ 里面找一个 $f[j]$ 的最大值。很容易想到使用数据结构来优化。

理论上我们可以使用权值线段树，但这里由于 $a[i]$ 的范围很大，其部分和 $S[j]$ 的范围就更大了，使用权值线段树容易超时。而且我们发现 $S[j]$ 是已知的且不变的，所以我们使用预处理离散化+树状数组会更好：先预处理出 $S$ 数组，然后从大到小排序后离散化，建立树状数组记录对应前缀和大小为 $S[j]$ 时，最大的 $f[j]$ 是多少。那么接下来每次查询时就是查询树状数组中某个前缀的最大值。时间复杂度为 $O(logRange*NlogN)$ 。期望得分 100 分。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
const int maxn=2e5+5;
ll a[maxn],f[maxn];
 
int bit[maxn*2+100];
void update(int x,int d){
    for(int i=x;i>0;i-=i&-i) bit[i]=max(bit[i],d);
}
int querysuf(int x,int B){
    int ret=-1e9;
    for(int i=x;i<B;i+=i&-i) ret=max(bit[i],ret);
    return ret;
}
void remove(int x,int B){
    for(int i=x;i<B;i+=i&-i) bit[i]=-1e9;
    for(int i=x;i>0;i-=i&-i) bit[i]=-1e9;
}
 
vector<ll> disc;
int getid(ll x){return lower_bound(disc.begin(),disc.end(),x)-disc.begin()+1;}
 
bool check(ll ans,int n,int k){// sum<=ans
    disc.clear();
    for(int i=1;i<=n;i++) {
        disc.push_back(a[i]);
        disc.push_back(a[i]-ans);
    }
    disc.push_back(0);
    sort(disc.begin(),disc.end());
    disc.erase(unique(disc.begin(),disc.end()),disc.end());
 
    for(int i=1;i<=disc.size();i++) remove(i,disc.size());
    f[0]=0;
    update(getid(0),f[0]);
    for(int i=1;i<=n;i++) {
        f[i]=querysuf(getid(a[i]-ans),disc.size()+1)+1;
        update(getid(a[i]),f[i]);
        if(f[i]>=k) return true;
    }
    return false;
}
 
int main(){
    int T; scanf("%d",&T);
    while(T--){
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++) {
            scanf("%lld",a+i);
            a[i]+=a[i-1];
        }
        ll l=-1e9*1e6,r=1e9*1e6;
        while(l+1<r){//  ans -> ( ]
            ll mid=(l+r)/2;//
            if(check(mid,n,k)) r=mid;//
            else l=mid;
        }
        printf("%lld\n",r);
    }
    return 0;
}