应动动要求，回cnblogs发篇博客。
首先从左往右枚举矩形的右边界，再从右往左枚举该右边界的左边界，[L, R]。
那么矩形们的面积就是$(R - L) * \sum h$。问题在于如何快速算出$\sum h$。
$h = y_{max} - y_{min}$。考虑从下往上枚举$y_{max}$，在左端点那条直线上存在最大的$y_{qaq} \le y_{max}$，而之前扫过的直线中的所有$y_i \in (y_{qaq}, y_{max})$都是有贡献的。小于第一个小于$y_{qaq}$的高度$y_{min}$的点都可以与这些$y_i$产生符合要求的矩形边长。设这种点有s个，只考虑一个y，它产生的边界的和就是$s * y - \sum \limits_{y_i \le y_{min}} y_i$。
把所有符合条件的y产生的边长累加起来，最后每个左边界产生的面积为：$\sum(R - L) * (s_{y_i \le y_{min}的数量} * \sum \limits_{y_i \in (y_{qaq}, y_{max})} - \sum \limits_{y_i \le y_{min}} y_i * s_{y_i \in (y_{qaq}, y_{max})})$。$y_{max}$是每个枚举的左边界从下向上枚举得到的。
长度和和数量和都可以用树状数组快速求出。
我知道动动在等我的代码时刻
#include <bits/stdc++.h> const int D = 1e9 + 7; int n, c[2510], pos[2510][2510]; bool used[2510]; struct Bit { int t[2510]; void add(int x, int d) { for (; x <= 2510; x += x & -x) t[x] += d; } int ask(int x) { int ret = 0; for (; x; x -= x & -x) ret += t[x]; return ret; } void clear() { for (int i = 1; i <= 2510; ++i) t[i] = 0; } } siz, len; inline int read() { int a = 0, b = 0; char c = getchar(); while (!isdigit(c)) b = c == '-' ? 1 : 0, c = getchar(); while (isdigit(c)) a = a * 10 + c - '0', c = getchar(); return b ? -a : a; } void modify(int x) { if (!used[x]) { used[x] = true; siz.add(x, 1), len.add(x, x); } } signed main() { n = read(); for (int i = 1, x, y; i <= n; ++i) x = read(), y = read(), pos[x][++c[x]] = y; for (int i = 1; i <= 2500; ++i) std::sort(pos[i] + 1, pos[i] + 1 + c[i]), pos[i][c[i] + 1] = 2501; long long ans = 0; for (int i = 1; i <= 2500; ++i) { if (!c[i]) continue; siz.clear(), len.clear(); for (int j = 1; j 2500; ++j) used[j] = false; for (int j = 1; j <= c[i]; ++j) modify(pos[i][j]); for (int j = i - 1; j; --j) { if (!c[j]) continue; int p1 = 1, p2 = 1, cur = std::max(pos[i][1], pos[j][1]); for (int k = 1; k <= c[j]; ++k) modify(pos[j][k]); while (pos[i][p1 + 1] <= cur) ++p1; while (pos[j][p2 + 1] <= cur) ++p2; while (p1 <= c[i] && p2 <= c[j]) { int mn = std::min(pos[i][p1], pos[j][p2]); int trend = std::min(pos[i][p1 + 1], pos[j][p2 + 1]); (ans += (long long) (i - j) * ((long long) (len.ask(trend - 1) - len.ask(cur - 1)) * siz.ask(mn) - (long long) (siz.ask(trend - 1) - siz.ask(cur - 1)) * len.ask(mn))) %= D; cur = trend; if (pos[i][p1 + 1] <= cur) ++p1; if (pos[j][p2 + 1] <= cur) ++p2; } } } return !printf("%lld\n", ans); }