#邮件 @sevenstd
2026-08-04 20:59:54
发布于：浙江
9阅读
0回复
0点赞
哥么这是发你的代码
@sevenstd
@sevenstd
@sevenstd
@sevenstd
@sevenstd
#include<bits/stdc++.h>
using namespace std;
int t;
int n,k;
int a[100005];
int tr[100005];
int rk[100005];
int lowbit(int x){
return x&-x;
}
long long query(int x){
long long ans=0;
while(x>=1){
ans+=tr[x];
x-=lowbit(x);
}
return ans;
}
void ud(int x,int k){
while(x<=n){
tr[x]+=k;
x+=lowbit(x);
}
}
bool check(long long mid){
int cnt=1;
int last=1;
long long sum=0;
for(int i=1;i<=n;i++){
long long dui=query(n)-query(rk[i]);
if(sum+dui>mid){
sum=0;
cnt++;
for(int j=last;j<=i-1;j++){
ud(rk[j],-1);
}
last=i;
}else{
sum+=dui;
}
ud(rk[i],1);
}
for(int i=last;i<=n;i++){
ud(rk[i],-1);
}
return cnt>k;
}
int main(){
cin>>t;
while(t--){
cin>>n>>k;
set<int>st;
for(int i=1;i<=n;i++){
tr[i]=0;
cin>>a[i];
rk[i]=0;
st.insert(a[i]);
}
map<int,int>mp;
int idx=0;
for(auto it:st){
idx++;
mp[it]=idx;
}
for(int i=1;i<=n;i++){
rk[i]=mp[a[i]];
}
// for(int i=1;i<=n;i++){
// int x=i-1-query(rk[i]);
// sum[i]=sum[i-1]+x;
// ud(rk[i],1);
// }
long long l=0,r=1e10,ans=0;
while(l<=r){
int mid=(l+r)/2;
if(check(mid)){
l=mid+1;
}else{
r=mid-1;
ans=mid;
}
}
cout<<ans<<endl;
}
return 0;
}
这里空空如也
有帮助，赞一个