求助

#3 WA

#include <bits/stdc++.h>
#define int long long
#define N 100005

//#undef N
//#define N 15

using namespace std;

inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	while (ch > '9' or ch < '0') {
		if (ch == '-') {
			f = -f;
		}
		ch = getchar();
	}
	while (ch >= '0' and ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

void write(int x) {
	if (!x)
		return;
	write(x / 10);
	putchar(x % 10 + '0');
}

struct node {
	int val, id;
	bool operator<(const node &a)const {
		return val < a.val;
	}
} a[N];

int T, n, k;
int b[N], c[N];

int lowbit(int x) {
	return x & (-x);
}

void add(int p, int  x) {
	while (p <= n) {
		b[p] += x;
		p += lowbit(p);
	}
}

int getsum(int p) {
	int res = 0;
	while (p) {
		res += b[p];
		p -= lowbit(p);
	}
	return res;
}

int getsum(int l, int r) {
	return getsum(r) - getsum(l - 1);
}

bool check(int mid) {
	memset(b, 0, sizeof(b));
	int cnt = 1;
	int sum = 0;
	int l = 1;
	for (int i = 1; i <= n; i++) {
		int temp = getsum(c[i], n);

		if (sum + temp > mid) {
//			l = i;
			cnt++;
			sum = 0;
//			memset(b, 0, sizeof(b));
			for (int j = l; j < i; ++ j) {
				add(c[j], -1);
			}
			l = i;
		} else
			sum += temp;
		add(c[i], 1);
	}
//	if(sum)
//		cnt++;
	if (cnt > k)
		return 0;
	else
		return 1;
}

signed main() {
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);
//	cin >> T;
	T = read();
	while (T--) {
		memset(b, 0, sizeof(b));
		memset(a, 0, sizeof(a));
		memset(c, 0, sizeof(c));

//		cin >> n >> k;
		n = read();
		k = read();

		for (int i = 1; i <= n; i++) {
//			cin >> a[i].val;
			a[i].val = read();
			a[i].id = i;
		}

		sort(a + 1, a + n + 1);

		int cnt = 0;
		a[0].val = 0x3f3f3f3f;
		
		for (int i = 1; i <= n; i++) {
			if (a[i].val != a[i - 1].val) cnt++;
			c[a[i].id] = cnt;
		}

//		int ans = 0;
		int l = 0, r = n * n;
		while (l < r) {
			int mid = (l + r) / 2;
			if (check(mid)) {
				r = mid;
//				ans = mid;
			} else
				l = mid + 1;
		}

//		cout << l << '\n';
		if (l != 0)
			write(l);
		else
			putchar('0');
		putchar('\n');
	}
	return 0;
}

/*
2
5 2
1 3 2 5 4
8 2
4 2 3 6 7 1 8 5
*/