10.30T2 二分+前缀和（后缀和）

Description

有两个队伍A和B，每个队伍都有n个人。这两支队伍之间进行n场1对1比赛，每一场都是由A中的一个选手与B中的一个选手对抗。同一个人不会参加多场比赛，每个人的对手都是随机而等概率的。例如A队有A1和A2两个人，B队有B1和B2两个人，那么(A1 vs B1,A2 vs B2)和(A1 vs B2,A2 vs B1)的概率都是均等的50%。
每个选手都有一个非负的实力值。如果实力值为X和Y的选手对抗，那么实力值较强的选手所在的队伍将会获得(X-Y)^2的得分。
求A的得分减B的得分的期望值。

Input

第一行一个数n表示两队的人数为n。
第二行n个整数，第i个数A[i]表示队伍A的第i个人的实力值。
第三行n个整数，第i个数B[i]表示队伍B的第i个人的实力值。

Output

输出仅包含一个实数表示A期望赢B多少分。答案保留到小数点后一位（注意精度）。

Sample Input

3 7

1 5

Sample Output

20.0

Hint

【数据规模】
对于30%的数据，n≤50。
对于100%的.据,n≤50000;A[i],B[i]≤50000。

code:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<iomanip>
 5 #define N 100006 
 6 using namespace std;
 7 long long a[N],b[N],sqsuma[N],sqsumb[N],suma[N],sumb[N];
 8 int main() {
 9     int n;
10     cin>>n;
11     for(int i=1; i<=n; i++) {
12         cin>>a[i];
13     }
14     for(int i=1; i<=n; i++) {
15         cin>>b[i];
16     }
17     sort(a+1,a+n+1);
18     sort(b+1,b+n+1);
19     for(int i=n;i>=1;i--){
20         sqsuma[i]=sqsuma[i+1]+a[i]*a[i];
21         suma[i]=suma[i+1]+a[i];
22         sqsumb[i]=sqsumb[i+1]+b[i]*b[i];
23         sumb[i]=sumb[i+1]+b[i];
24     }
25     long long A=0,B=0;
26     for(int i=1;i<=n;i++){
27         int pos=upper_bound(b+1,b+n+1,a[i])-b;
28         long long now1=sqsumb[pos];
29         long long now2=(n-pos+1)*a[i]*a[i];
30         long long now3=2*sumb[pos]*a[i];
31         A+=now1+now2-now3;
32         now1=(sqsumb0[1]-sqsumb[pos]);
33         now2=(pos-1)*a[i]*a[i];
34         now3=2*(sumb[1]-sumb[pos])*a[i];
35         B+=now1+now2-now3;
36     }
37     cout<<fixed<<setprecision(1)<<(long double)(B-A)*1.0/n;
38     return 0;
39 }

over