不想用树状数组来写，用归并排序

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N = 1e5+10;

int w[N],a[N],b[N];
int T,n,k;
int ans;

void mmsort(int l,int r){
    if(l==r)return;
    
    int mid=(l+r)>>1;
    mmsort(l,mid),mmsort(mid+1,r);
    
    int i=l,j=mid+1,k=l;
    
    while(i<=mid&&j<=r){
        if(a[i]<=a[j])b[k++]=a[i++];
        else{
            b[k++]=a[j++];
            ans+=mid-i+1;
        }
    }
    
    while(i<=mid)b[k++]=a[i++];
    while(j<=r)b[k++]=a[j++];
    
    for(int i=l;i<=r;i++){
        a[i]=b[i];
    }
}

bool check(int x){
    int now=1,cnt=1;
    //区间为i~now
    for(int i=1;i<=n;i++){
        ans=0;
        for(int j=1;j<=n;j++){
            a[j]=w[j];
        }
        mmsort(now,i);
        // cout<<now<<" "<<i<<" "<<ans<<endl;
        if(ans>x){
            now=i;
            cnt++;
        }
    }
    
//   cout<<"cnt="<<cnt<<endl;
    return cnt<=k;
}

int main(){
    // cin>>T;
    scanf("%d",&T);
    
    while(T--){
        memset(b,0,sizeof b);
        
        ans=0;
        // cin>>n>>k;
        scanf("%d%d",&n,&k);
        if(n==1){
            puts("0");
            continue;
        }
        for(int i=1;i<=n;i++){
            // cin>>w[i];
            scanf("%d",&w[i]);
            a[i]=w[i];
        }
        // sort(a+1,a+n+1);
        // int m=unique(a+1,a+n+1)-a-1;
        // for(int i=1;i<=n;i++) w[i]=lower_bound(a+1,a+m+1,w[i])-a;
        
        mmsort(1,n);
        
        int l=-1,r=ans+1;
        // cout<<ans<<endl;
        
        while(l+1!=r){
            int mid=(l+r)>>1;
            if(check(mid))r=mid;
            else l=mid;
        }
        
        // cout<<r<<endl;
        printf("%d\n",r);
        
    }
    
    return 0;
}