解题思路

​ 假设塔子哥选的点是 $(x_1, y_1)$ ，岁阳选的点是 $(x_2, y_2)$，那么满足塔子哥能抓到岁阳的条件是：$x_1 \ge x_2 \ and \ y_1\ge y_2$，最终的答案就是所有满足这样关系的点对个数。

​ 由于 $x$ 轴和 $y$ 轴是独立的，我们这边只需要单独讨论，设所有纵坐标满足的方案数为 $b$ 。

​ 假设对于给定的横坐标 $X_1$ 来说有 $a$ 个满足的条件的（即 $\sum_{i = 1}^{i = n}(x_i <= X_1)$）个数，那么对答案的贡献为 $a \times b$ 。

​ 对于 $a$ 的计算，可以先将所有值存在哈希表中，然后再对横纵坐标从小到大进行排序，对于遍历到第 $i$ 个元素，显然前面有 $i$ 个元素都比它小( $i$ 从 0 开始)，还需要考虑与其相等的元素个数。最终 $a = i + cnt[x_i]$ ，$cnt[x_i]$ 表示当前 $x_i$ 出现的次数，每次计算完后 $cnt[x_i]$ 要减一，为了避免重复计算，对于 $b$ 的计算也是同理。

代码

• CPP

#include<bits/stdc++.h>

using namespace std;

#define int long long

signed main (){
  int n, m; cin >> n >> m;
  vector<int> a(n), b(m);
  unordered_map<int, int> l, r;

  // 读入数据并计数
  for(int i = 0; i < n; i ++) cin >> a[i], l[a[i]]++;
  for(int i = 0; i < m; i ++) cin >> b[i], r[b[i]]++;

  // 对序列排序
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());

  int res = 0; // 结果
  int t = 0; // 用于计算 y 坐标情形数量

  // 计算 y 坐标情形数量
  for(int i = 0; i < m; i ++) 
      t += i + r[b[i]], r[b[i]]--;

  // 计算 x 坐标情形数量并累加到结果
  for(int i = 0; i < n; i ++)
  {
      int k = i + l[a[i]];
      l[a[i]]--;
      res += k * t;
  }

  cout << res << "\n"; // 输出结果
}

题目描述

岁阳是一种不具固定形体的能量生物。一些不怀好意的岁阳会扰乱正常的社会秩序。现在，米小游被委派捉拿岁阳。

米小游会选择一个点$(x1,y1)$，以$(0,0)$为左下角，$(x1,y1)$为右上角，平行于坐标轴，构成一个矩形陷阱，如果岁阳位于这个短形内部或边界上，就可以成功捉拿岁阳。岁阳的位置被记作$(x2,y2)$

下面，给出坐标$(x,y)$的构成方法: 给定一个长度为$n$的整数序列$a$，和一个长度为$m$的整数序列$b$，从a中选择其中一个数字作为$x$,从$b$中选择一个数字作为$y$，这样可以得到一组坐标$(x,y)$。

米小游所选择的$(x1,y1)$和和岁阳的位置$(x2,y2)$均通过上述办法产生,

你的任务是计算在所有可能的情形中，米小游能够成功捉拿岁阳的情形数量。

输入描述

第一行两个整数 n和 m，分别表示数组 a和 b的长度。 第二行 n个整数 $a_1,a_2 … a_n$，表示序列 a。 第三行 m 个整数 $b_1,b_2, …bm$，表示序列 b。 对于全部数据，$1≤n,m\le 5\times 10^4$,$1≤a,b\le 10^9$

输出描述

输出一行，一个整数，表示答案。

样例输入

3 3
1 2 3
1 1 3

样例输出

42

说明

当米小游选择的位置是(1，1)，岁阳选择的位置是(1，3)时，米小游无法成功捉拿岁阳
当米小游选择的位置是(2，3)，岁阳选择的位置是(2，1)时，藿可以成功捉拿岁阳.类似的情况共有 42 种，因此输出 42。