树状数组+二分
就是找第几小的数，，找几次，再求和。
。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
const int N=277777;
int t,n,m,bit[N],num,i;
long long ans;
int low(int g)
{
return g&(-g);
}
void update(int pos)
{
while(pos<=n)
{
bit[pos]--;
pos+=low(pos);
}
}
int query(int x)
{
int sum=0;
while(x>0)
{
sum+=bit[x];
x-=low(x);
}
return sum;
}
int Sum(int k)
{
int l=1,r=n,mid;
while(l<r)
{
mid=(l+r)>>1;
if(query(mid)>=k)
r=mid;
else
l=mid+1;
}
return l;
}
void init()
{
ans=0;
memset(bit,0,sizeof(bit));
scanf("%d %d",&n,&m);
for(i=1;i<=n;i++)
{bit[i]=low(i);}
for(i=0;i<m;i++)
{
scanf("%d",&num);
int s=Sum(num);
update(s);
ans+=s;
}
}
int main()
{
int cas=0;
scanf("%d",&t);
while(t--)
{
init();
cout<<"Case "<<++cas<<": "<<ans<<endl;
}
return 0;
}
二分查找具体解释点击打开链接