题解 CF1194E 【Count The Rectangles】
Heartlessly
2019-07-16 16:05:16
## 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])$
## 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
```cpp
#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
```cpp
#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;
}
```