题意
农夫约翰让他的 n (1 leq n leq 100,000) 头牛在长度为 c 的跑道上进行跑 l 圈的比赛，所有牛从同一起点，以不同的速度开始跑。直到当跑得最快的那一头牛跑完 l 圈时，所有牛才同时停下。 约翰发现在跑圈过程中发生了几次“超越事件”。其定义是：在比赛结束前某时刻，奶牛 x 已经超越了奶牛 y 整整一圈，则称做一次“超越事件”。（注： 至少一圈 ，超越了frac{1}{2}圈，或者超越了frac{1}{4}圈等等都不算。且对于同一对奶牛(x,y)不会重复计算次数。） 约翰想知道比赛过程中发生了多少次“超越事件”。
思路
设第i头奶牛跑了a_i圈，显而易见，a_i=v[i]*(ldiv Max)，其中Max为最大速度。 那么将奶牛按照跑的圈数从大到小排序，显而易见答案就是lfloor a_i - a_j rfloor(i<j)O(N^2)的程序跑出很好的成绩了 那么想办法优化这个式子，通过乱搞发现lfloor a_i rfloor - lfloor a_j rfloor(i<j)1。 那什么时候会相差1呢？举个栗子，当a_i=2.5,a_j=1.9时，这个式子就会多算1。但这个式子绝对不会少算。于是我们只要额外统计下多算的情况就好了。不难发现，当小数部分是逆序对时，此时就多算了。 所以把a_i分成整数部分f[i].a与余数部分f[i].b。（为什么不是小数部分呢？因为小数部分比较难以控制——精度问题严重，而除数都是一样的，都是Max，所以就用余数更简单啦） 接下来就是套树状数组求逆序对的板子了。 等等，你问我不多算的式子怎么求？直接统计个前缀和乱搞就好了呀…
Code
代码语言：javascript复制#include<algorithm>
#include<bitset>
#include<complex>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<cmath>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
using namespace std;
#define re
#define int long long
#define LD double
class Quick_Input_Output{
private:
static const int S=1<<21;
#define tc() (A==B&&(B=(A=Rd) fread(Rd,1,S,stdin),A==B)?EOF:*A )
char Rd[S],*A,*B;
#define pc putchar
public:
#undef gc
#define gc getchar
inline int read(){
int res=0,f=1;char ch=gc();
while(ch<'0'ch>'9'){if(ch=='-') f=-1;ch=gc();}
while(ch>='0'&&ch<='9') res=res*10 ch-'0',ch=gc();
return res*f;
}
inline void write(int x){
if(x<0) pc('-'),x=-x;
if(x<10) pc(x '0');
else write(x/10),pc(x '0');
}
#undef gc
#undef pc
}I;
#define File freopen("tmp.in","r",stdin);freopen("tmp.out","w",stdout);
struct node{
int a,b;
}f[100010];
inline int cmp(node x,node y){return x.a<y.a(x.a==y.a&&x.b<y.b);}
class Array_Tree{//树状数组求逆序对
private:
int c[1000010];
public:
inline void add(int x,int y){for(;x<=1000000;x =(x&(-x))) c[x] =y;}
inline int getsum(int x){re int s=0;for(;x>=1;x-=(x&(-x))) s =c[x];return s;}
inline int query(int l,int r){return getsum(r)-getsum(l);}
}T;
class Solve{
private:
int n,l,c,v[100010],ans,Max;
public:
inline bool init(){
n=I.read();l=I.read();c=I.read();
for(int i=1;i<=n;i ) v[i]=I.read(),Max=max(Max,v[i]);
for(int i=1;i<=n;i ) f[i].a=v[i]*l/Max,f[i].b=v[i]*l%Max;//整数部分和小数部分
}
inline void solve(){
sort(f 1,f n 1,cmp);
for(int sum=0,i=1;i<=n;i ){
ans =(f[i].a*(i-1)-sum)-T.query(f[i].b,1000000);//非多算部分-多算部分
sum =f[i].a;//更新前缀和
if(f[i].b>0) T.add(f[i].b,1);//树状数组上传
}
I.write(ans);putchar('n');
}
}S;
signed main(){
// File
S.init();
S.solve();
}
