WA求条，代码清晰易懂

#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
using namespace std;
const int _ = 1e5 + 5;

int n,k,T;
int a[_],b[_];
map <long long,int> Map; 
int c[_ << 1];
void update(int x,int k)
{
    for(;x <= n;x += lowbit(x))
        c[x] += k;  
}

int query(int x)
{
    int ans = 0;
    for(;x;x -= lowbit(x))
        ans += c[x];
    return ans;
}

bool check(int ans)
{
	memset(c,0,sizeof c);
	stack <int> s;
	int num = 0;
	int sum = 1;//分段数量 
	for(int i = 1;i <= n;i++)
	{
		num += query(n) - query(a[i]);
		if(num > ans)
		{
			sum++;
			while(!s.empty())//还原 
			{
				update(s.top(),-1);
				s.pop();
			}
			num = 0; 
		}
		update(a[i],1);
		s.push(a[i]);
	}
	return sum <= k;
}

int main()
{
	ios::sync_with_stdio(false);
	cin >> T;
	while(T--)
	{
		Map.clear();
		Map[0] = 0;
		b[0] = 0;
		cin >> n >> k;
		for(int i = 1;i <= n;i++)
		{
			cin >> a[i];
			b[i] = a[i];
		}
		sort(b + 1,b + n + 1);
		for(int i = 1;i <= n;i++)
		{
			if(!Map[b[i]])
				Map[b[i]] = Map[b[i - 1]] + 1;
		 }
		for(int i = 1;i <= n;i++)
		{
			a[i] = Map[a[i]];
//			cout << a[i] << " ";
		}
			
		int l = 0,r = 1e9;
//		cout << check(0) << " ";
		while(l < r)
		{
			int mid = (l + r) >> 1;
			if(check(mid)) r = mid;
			else l = mid + 1;
		}
		cout << l << endl;
	}
	return 0;
}