由于是一个二次函数的关系，所以易证应该尽量让两组的顺序相同
然后就离散化乱搞几发，最后就变成了求逆序对的数量了
1 #include<bits/stdc++.h> 2 #define pa pair<int,int> 3 #define ll long long 4 using namespace std; 5 const int maxn=100010,mod=99999997; 6 7 inline ll rd(){ 8 ll x=0;char c=getchar();int neg=1; 9 while(c<'0'||c>'9'){if(c=='-') neg=-1;c=getchar();} 10 while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); 11 return x*neg; 12 } 13 14 int N; 15 pa h1[maxn],h2[maxn]; 16 int nh[maxn],rank[maxn]; 17 int tr[maxn]; 18 19 inline int lowbit(int x){return x&(-x);} 20 21 inline void add(int x,int y){ 22 for(;x<=N;x+=lowbit(x)) tr[x]=(tr[x]+y)%mod; 23 } 24 inline int query(int x){ 25 int re=0;for(;x;x-=lowbit(x)) re=(re+tr[x])%mod;return re; 26 } 27 28 int main(){ 29 int i,j,k; 30 N=rd(); 31 for(i=1;i<=N;i++) h1[i]=make_pair(rd(),i); 32 for(i=1;i<=N;i++) h2[i]=make_pair(rd(),i); 33 sort(h1+1,h1+N+1);sort(h2+1,h2+N+1); 34 for(i=1;i<=N;i++){ 35 rank[i]=h1[i].second; 36 }for(i=1;i<=N;i++){ 37 nh[h2[i].second]=rank[i]; 38 }int ans=0; 39 for(i=N;i;i--){ 40 ans=(ans+query(nh[i]))%mod; 41 add(nh[i],1); 42 }printf("%d ",ans); 43 return 0; 44 }