【题目描述】
今年，n只思考熊参加了清华大学校园马拉松比赛。马拉松的赛道是环形的，每圈
的长度是A，完成比赛需要跑L圈。
比赛中，甲领先乙很长距离，绕过一圈或多圈后从后面追上了乙的现象叫做“套
圈”。套圈现象非常常见，例如：跑得比谁都快的saffah熊可以套某些熊L-1圈；
ufozgg熊经常进行日常耐力训练，套圈次数和被套圈次数基本持平；而Mulab作为一
只老年熊，则是被套L-1圈的那种。
与人不同的是，思考熊在跑步时都是匀速运动。wyx熊是这次比赛的计时员，他
统计了参赛的n只熊的速度v1， v2，......，vn（其中最大的一个是saffah熊的速度）。现在
wyx熊希望你告诉他，当速度最快的saffah熊到达终点时，场上所有熊中总共发生了
多少次套圈现象。
注意：在saffah熊刚刚到达终点那一刻，如果甲恰好追上了乙，此时也算作甲将乙
套圈。
【输入格式】
从文件running.in中读入数据。
输入的第一行包含2个整数T;C，分别表示这个测试点内数据的组数和这个测试
点的编号。对于所有测试点，保证T = 10。
每组数据的第一行包含3个正整数n;A;L，分别表示思考熊的只数，跑道每圈的长
度和完成比赛所需要的圈数。保证A;L<10^8。
第二行包含n个正整数v1， v2，......，vn，表示每只思考熊的速度。保证这些数互不
相同。
【输出格式】
输出到文件running.out中。
输出T行，分别表示每组数据中，所有熊发生的套圈总次数。
【样例输入】
4 0
2 1000 15
2 5
2 1000 13
9 4
5 1000 10
8 10 2 5 6
5 1000 17
8 10 2 5 7
【样例输出】
9
7
38
61
【数据范围】
n<=105,vi<=108
【题解】
套圈的圈数只取决于每个人跑了多少圈，所以答案为两两之间的圈数差向下取整
因为有圈数小数部分，所以无法通过前缀和O（n）计算
但是，我们可以把小数部分和整数部分分开做
整数部分用前缀和维护圈数，如果小数部分的差小于0，就再减一
比如一个跑了5.1圈，一个4.9圈，他们整数部分差为5-4=1，但是因为小数部分0.1-0.9<0，所以需要减一
所以需要找出两个数i,j，整数部分i>j,但小数i<j
这就是逆序对棵题了，树状数组就能搞定。
还有一个小优化，因为跑的圈数是l*vi/vmax，分母都相同，可以全部去掉转化成整数计算，避免精度误差
（之前用小数存被精度误差卡成狗了.......）
【代码】
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<set>
using namespace std;
#define f(i,n) for(int i=1;i<=(n);i++)
#define ll long long
#define INF 1<<30
#define N 100010
#define c 32123
ll read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n;
ll v[N],f,l;
struct xj
{
double n;
int i;
}z[N];
double s;
bool cmp(xj a,xj b)
{
if(a.n==b.n)return a.i>b.i;
return a.n>b.n;
}
int szsz[N];
int lowbit(int x)
{
return x&-x;
}
void ass(int k)
{
while(k<=n)
{
szsz[k]++;
k+=lowbit(k);
}
}
int qj(int k)
{
int ans=0;
while(k>0)
{
ans+=szsz[k];
k-=lowbit(k);
}
return ans;
}
int main()
{
freopen("running.in","r",stdin);
freopen("running.out","w",stdout);
int t,C;
scanf("%d%d",&t,&C);
while(t--)
{
scanf("%d%lld%lld",&n,&f,&l);
f(i,n)v[i]=read();
sort(v+1,v+n+1);
ll ans=0,sum=0;
f(i,n)
{
ll temp=l*v[i]/v[n];
ans+=(i-1)*temp-sum;
sum+=temp;
z[i].n=l*v[i]-temp*v[n];
z[i].i=i;
}
memset(szsz,0,sizeof(szsz));
sort(z+1,z+n+1,cmp);
f(i,n)
{
ans-=qj(z[i].i);
ass(z[i].i);
}
printf("%lld\n",ans);
}
}