代码如下

#include<bits/stdc++.h>
#define int long long
using namespace std;
int t,n,k,cnt;
int a[400010],s[400010],tree[400010];
int lowbit(int x){return x&(-x);}
void update(int x,int y){
	for(;x<=n;x+=lowbit(x))
		tree[x]+=y;
}
int query(int x){
	int sum=0;
	for(;x>0;x-=lowbit(x))
		sum+=tree[x];
	return sum;
}
bool check(int x){
	int sum=1,cnt=0,l=n;
	for(int i=n;i>=1;i--){
		int t=query(a[i]-1);
		if(cnt+t>x){
			sum++,cnt=0;
			for(int j=l;j>i;j--)
				update(a[j],-1);
			l=i;
		}
		else cnt+=t;
		
		update(a[i],1);
	}
	for(int i=l;i>=1;i--)
		update(a[i],-1);
//	if(cnt!=0)sum++;
//	if(cnt>k)sum++;
//	printf("        %lld %lld\n",x,sum);
	return sum<=k;
}
signed main(){
	scanf("%lld",&t);
	while(t--){
		scanf("%lld%lld",&n,&k);
		cnt=0;
		for(int i=1;i<=n;i++){
			tree[i]=0;
			scanf("%lld",&a[i]);
			s[i]=a[i];
		}
		sort(s+1,s+n+1);
		cnt=unique(s+1,s+n+1)-(s+1);
		for(int i=1;i<=cnt;i++)
			a[i]=lower_bound(s+1,s+n+1,a[i])-s;
		cnt=0;
		int l=0,r=n*n,ans=0;
		while(l<=r){
			int mid=(l+r)>>1;
//			printf("%lld %lld %lld\n",l,r,mid);
			if(check(mid)){
				ans=mid;
				r=mid-1;
			} 
			else l=mid+1;
		}
		printf("%lld\n",ans);
	}
	
	return 0;
}

/*

*/