单选题：序列问题求满足 ai<aj 的对数 (C++代码补全)

三、 完善程序（单选题，每小题 3 分，共计 30 分）

(1)（序列问题） 给定序列 an，求有多少对 (i,j) 满足 ai<aj。 测试数据满足 n≤106， ai≤109。 提示： 对于任意的 ai≠ aj，可以发现 (i,j) 或 (j,i) 能对答案产生 1 的贡献， 因此我们只需要用总的对数减去 ai=aj 的 (i,j) 数量，就能得到答案。 试补全程序。

01 #include<bits/stdc++.h>
02 using namespace std;
03 const int Maxn = ①;
04 int n, a[Maxn];
05 long long s[Maxn], ans;
06 bool check(int l, int r) {
07 if (s[r] - s[l - 1] == ②) return true;
08 return false;
09 }
10 
11 
12 
13 int main() {
14 cin >> n;
15 for (int i = 1; i <= n; i ++)
16 cin >> a[i];
17 sort (a + 1, a + n + 1);
18 for (int i = 1; i <= n; i ++)
19 s[i] = s[i - 1] + a[i];
20 ans = ③;
21 for (int i = 1; i <= n;) {
22 int l = i, r = n, pos = n;
23 while (④) {
24 int mid = (l + r) >> 1;
25 if(check(l, mid))
26 l = mid + 1, pos = mid;
27 else
28 r = mid - 1;
29 }
30 ans -= ⑤;
31 i = pos + 1;
32 }
33 cout << ans;
34 }

34. ① 处应填（ ） 。 A. 1e6 + 7 B. 1000000 C. 1e6 D. 1000000000000

35. ② 处应填（ ） 。 A. (r - l + 1) * a[l] B. s[r] - s[l - 1] C. 1LL * (r–l+1) * a[l] D. a[1] = 0

36. ③ 处应填（ ） 。 A. n * (n + 1) / 2 B. 1ll * n * (n + 1) / 2 C. n * (n - 1) / 2 D. 1ll * n * (n - 1) / 2

37. ④ 处应填（ ） 。 A. l < r B. l <= r C. l <= r + 1 D. l > r

38. ⑤ 处应填（ ） 。 A. (pos - l + 1) * (pos - l) / 2 B. 1ll * (pos - l + 1) * (pos - l) / 2 C. (pos - i + 1) * (pos - i) / 2 D. 1ll * (pos - i + 1) * (pos - i) / 2

答案：

34. C. 1e6
35. B. s[r] - s[l - 1]
36. D. 1ll * n * (n - 1) / 2
37. C. l <= r + 1
38. B. 1ll * (pos - l + 1) * (pos - l) / 2