Rectangular Pasture (USACO Silver 2020 December)

首先坐标是可以离散化的。

然后我们理解需求：要求是FJ可以包围的奶牛的子集的数量，而条件关键点是每个 $x$ 和 $y$ 都是唯一的。这样组合起来，包围同一组奶牛的多个不同的栅栏只计算一次，所以可以归一化成其中最小的那个，就是四个边上各有一头奶牛的那个。

此题可以有很多种解法。下面的解法是枚举上下两个边界上的两头牛 $i$ 和 $j$ 。这两头牛确定之后，就确定了上下边界和左右边界的范围，左右边界是有很多可能性的，所有位于 $i$ 和 $j$ 的两边的，如下图所示l和r的牛都是合法的，而x的牛是不合法的。通过二维前缀和可以把l和r的数量求出来，乘起来就是 $i$ 和 $j$ 一共贡献的结果。

               x          
      x
----------i---------------------
  l       |         |   
          |         |        r
     l    |         |        
          |         |     r
          |       x |
       l  |         |     
--------------------j-----------
                        x
             x

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
struct P {
    int x;
    int y;
};
P p[2505];
 
bool xcmp(P &a, P &b) { return a.x < b.x;}
bool ycmp(P &a, P &b) { return a.y < b.y;}
 
int v[2505][2505];
int psum[2505][2505];   // psum[y+1][x+1]
 
long long ans;
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &p[i].x, &p[i].y);
    // 压缩到[1,n]
    sort(p, p+n, xcmp);
    for (int i = 0; i < n; i++)
        p[i].x = i+1;
    sort(p, p+n, ycmp);
    for (int i = 0; i < n; i++)
        p[i].y = i+1;
    for (int i = 0; i < n; i++)
        v[p[i].y][p[i].x] = 1;
 
    for (int y = 1; y <= n; y++)
        for (int x = 1; x <= n; x++)
            psum[y][x] = v[y][x] + psum[y-1][x] + psum[y][x-1] - psum[y-1][x-1];
 
    int x1, x2, y1, y2, l ,r;
    ans = n+1;
    for (int i = 0; i < n; i++)
        for (int j = i+1; j < n; j++) {
            x1 = min(p[i].x, p[j].x);
            x2 = max(p[i].x, p[j].x);
            y1 = min(p[i].y, p[j].y);
            y2 = max(p[i].y, p[j].y);
            // 固定y1,y2的情况下，计算左侧区域有多少个x <= x1 (l), 右侧有多少个x>=x2 (r)
            // 则有l*r个unique的组合
            l = psum[y2][x1]-psum[y1-1][x1];
            r = psum[y2][n]-psum[y2][x2-1]-psum[y1-1][n]+psum[y1-1][x2-1];
            ans += (long long)l * r;
        }
 
    printf("%lld\n", ans);
 
    return 0;
}