Luogu P3054 [USACO12OPEN]跑圈Running Laps 题解

#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%10+'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();
}