「Codeforces 1194E」Count The Rectangles

Description

二维坐标系上有 $n$ 条线段，每条线段连接 $(x_{i,1},y_{i,1}),(x_{i,2},y_{i,2})$ 两个整点，且所有线段平行于坐标轴，保证平行于同一条坐标轴的线段不相交。求这些线段能组成多少个矩形。

$(1 \leq n \leq 5 \times 10^3,x,y \in [-5 \times 10^3,5 \times 10^3])$

Source

Solution 1

暴力做法。先把横线和竖线分开存储，我们可以 $O(n^2)$ 预处理出与第 $i$ 条横线相交的竖线集合为 $f_i$ 。接下来枚举矩形的上下两条边为第 $i$ 条横线和第 $j$ 条横线，那么同时与这两条横线相交的竖线集合为 $f_i \cap f_j$，假设这个集合的大小为 $x$，则能形成 ${\rm C}_x^2$ 个矩形，累加就能得到答案。显然可以用 $\rm bitset$ 优化，时间复杂度为 $O(\frac{n^3}{w})$ 。但是这样写当横线数量大时会被卡掉，所以可以特判一下横线竖线哪个多，如果横线较多，就反过来预处理横线集合，枚举竖线。

Code 1

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 5e3, MAXM = 2500;
int n, cnt1, cnt2;
LL ans;
struct Node {
    int x1, y1, x2, y2;
} row[MAXN + 5], col[MAXN + 5];
bitset<MAXN + 5> f[MAXM + 5];

int main() {
    read(n);
    for (int x1, y1, x2, y2, i = 1; i <= n; ++i) {
        read(x1), read(y1), read(x2), read(y2);
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        if (y1 == y2) row[++cnt1] = (Node) { x1, y1, x2, y2 };
        else col[++cnt2] = (Node) { x1, y1, x2, y2 };//分开存储 
    }
    if (cnt1 < cnt2) {//竖线较多 
        for (int i = 1; i <= cnt1; ++i)
            for (int j = 1; j <= cnt2; ++j)
                if (row[i].x1 <= col[j].x1 && row[i].x2 >= col[j].x1 && 
                col[j].y1 <= row[i].y1 && col[j].y2 >= row[i].y2)
                    f[i][j] = 1;//第 i 条横线与第 j 条竖线相交
        for (int i = 1; i <= cnt1; ++i)
            for (int j = i + 1; j <= cnt1; ++j) {
                int t = (f[i] & f[j]).count();//同时与 i,j 相交的竖线数量 
                ans += 1ll * t * (t - 1) >> 1;
            }
    } else {//横线较多 
        for (int i = 1; i <= cnt1; ++i)
            for (int j = 1; j <= cnt2; ++j)
                if (row[i].x1 <= col[j].x1 && row[i].x2 >= col[j].x1 && 
                col[j].y1 <= row[i].y1 && col[j].y2 >= row[i].y2)
                    f[j][i] = 1;//第 j 条横线与第 i 条竖线相交
        for (int i = 1; i <= cnt2; ++i)
            for (int j = i + 1; j <= cnt2; ++j) {
                int t = (f[i] & f[j]).count();//同时与 i,j 相交的横线数量 
                ans += 1ll * t * (t - 1) >> 1;
            }
    }
    write(ans);
    putchar('\n'); 
    return 0;
}

Solution 2

考虑将横线按 $y$ 坐标从小到大排序，竖线按上端点的 $y$ 坐标从小到大排序。然后枚举矩形下面的边为第 $i$ 条横线，把所有与该横线相交的竖线存到队列里，用树状数组维护区间竖线数量。接着枚举矩形上面的边为第 $j$ 条横线（在第 $i$ 条横线的上方），对于队列里上端点在第 $j$ 条横线下方的竖线，我们可以在树状数组中把它删掉，因为它不与第 $j$ 条横线相交。由于队列里竖线的上端点单调递增，这步操作可以线性解决。对于每对 $i,j$，用树状数组查询区间竖线数量，统计答案。注意树状数组的下标不能为非正数，所以给所有初始坐标加上一个较大的整数，时间复杂度 $O(n^2 \log n)$ 。

Code 2

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 5e3, MAXM = 1e4 + 1;
int n, cnt1, cnt2, q[MAXN + 5];
LL ans;
struct Node {
    int x1, y1, x2, y2;
    
    inline friend bool operator<(Node x, Node y) {
        return x.y2 < y.y2;
    }
} row[MAXN + 5], col[MAXN + 5];
struct BinaryIndexTree {//树状数组 
    int ind[MAXM + 5];
    
    inline void clear() {
        memset(ind, 0, sizeof (ind));
    }
    inline void add(int x, int p) {
        for (; x <= MAXM; x += x & -x) ind[x] += p;
    }
    inline int query(int x) {
        int res = 0;
        for (; x; x -= x & -x) res += ind[x];
        return res;
    }
    inline int query(int l, int r) {
        return query(r) - query(l - 1);
    }
} bit;

int main() {
    read(n);
    for (int x1, y1, x2, y2, i = 1; i <= n; ++i) {
        read(x1), read(y1), read(x2), read(y2);
        x1 += MAXN + 1, y1 += MAXN + 1, x2 += MAXN + 1, y2 += MAXN + 1;//防止出现负数 
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
        if (y1 == y2) row[++cnt1] = (Node) { x1, y1, x2, y2 };
        else col[++cnt2] = (Node) { x1, y1, x2, y2 };
    }
    sort(row + 1, row + cnt1 + 1), sort(col + 1, col + cnt2 + 1);
    for (int i = 1; i <= cnt1; ++i) {//枚举矩形下面的边 
        bit.clear();//清空树状数组 
        int tail = 0, k = 1;
        for (int j = 1; j <= cnt2; ++j)
            if (row[i].x1 <= col[j].x1 && row[i].x2 >= col[j].x1 && 
            col[j].y1 <= row[i].y1 && col[j].y2 >= row[i].y2) {
                //与第 i 条横线相交 
                bit.add(col[j].x1, 1);//树状数组单点修改 
                q[++tail] = j;//存入队列 
            }
        for (int j = i + 1; j <= cnt1; ++j) {//枚举矩形上面的边 
            for (; col[q[k]].y2 < row[j].y1 && k <= tail; ++k)// k 单调递增 
                bit.add(col[q[k]].x1, -1);//删去队列中不与 j 相交的竖线
            int l = max(row[i].x1, row[j].x1), r = min(row[i].x2, row[j].x2);
            if (l < r) {//两条线段有交 
                int res = bit.query(l, r);//[l, r] 区间内的竖线能与 i,j 组成矩形 
                ans += 1ll * res * (res - 1) / 2;//统计答案 
            }
        }
    }
    write(ans);
    putchar('\n');
    return 0;
}