在坐标系上给定一些平行于 \(x\) 轴 或 \(y\) 轴 的线段，求一共能围成多少个不同的矩形
\(n\leq5000, |x|,\ |y|\in[0,\ 5000]\)
乱搞，bitset
这是一篇 非正解
令 \(n1=\) 平行于 \(y\) 轴的线段数， \(n2=\) 平行于 \(x\) 轴的线段数
考虑任意两条平行于 \(y\) 轴的线段对答案的贡献，令 \(s=\) 同时与两条线段相交的平行于 \(x\) 轴的线段数，贡献即为 \(\frac{s(s-1)}{2}\)
可以考虑枚举每两条平行于 \(y\) 轴的线段，统计答案可以考虑对于每条平行于 \(y\) 轴的线段，预处理与之相交的平行于 \(x\) 轴的线段并用 bitset 存储，之后暴力 bitset 操作
时间复杂度 \(O(\frac{n^3}{w})\) ，仍然跑不过
可以发现这个做法的时间复杂度瓶颈在于每次 bitset 操作的时间复杂度都是 \(\frac{5000}{w}\) 的，而我们只需要统计 bitset 前 \(n2\) 位，可以考虑 手写 bitset
考虑这样做的最坏时间复杂度，把 \(n1\) 取到 \(3333\) ，大概会跑 \(3333^2\times(5000-3333)/64/2\approx1.4\times10^8\) 次，cf机子两秒完全不虚
时间复杂度 \(O(\frac{n^3}{w})\)
代码
#includeusing namespace std;const int maxn = 5010;int n, n1, n2, tot;struct node1 { int x, y1, y2;} a[maxn];struct node2 { int x1, x2, y;} b[maxn];typedef unsigned long long u64;struct Bitset { u64 s[maxn >> 6]; inline void set(int x) { s[x >> 6] |= 1llu << (x & 63); }} tmp, f[maxn];inline int add(int x, int y) { int ans = 0; for (register int i = 0; i <= tot; ++i) { ans += __builtin_popcountll(f[x].s[i] & f[y].s[i]); } return ans;}int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) { int x1, x2, y1, y2; scanf("%d %d %d %d", &x1, &y1, &x2, &y2); if (x1 == x2) { if (y1 > y2) swap(y1, y2); a[++n1] = node1{x1, y1, y2}; } else { if (x1 > x2) swap(x1, x2); b[++n2] = node2{x1, x2, y1}; } } tot = n2 >> 6; for (int i = 1; i <= n1; ++i) { for (int j = 1; j <= n2; ++j) { if (b[j].x1 <= a[i].x && a[i].x <= b[j].x2 && a[i].y1 <= b[j].y && b[j].y <= a[i].y2) { f[i].set(j); } } } long long ans = 0; for (int i = 1; i < n1; ++i) { for (int j = i + 1; j <= n1; ++j) { int s = add(i, j); ans += s * (s - 1); } } printf("%I64d", ans >> 1); return 0;}