CF1194E Count The Rectangles

CF1194E Count The Rectangles

在坐标系上给定一些平行于 (x) 轴 或 (y) 轴 的线段，求一共能围成多少个不同的矩形

(nleq5000,|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^2times(5000-3333)/64/2approx1.4times10^8) 次，cf机子两秒完全不虚

时间复杂度 (O(frac{n^3}{w}))

代码

#include <bits/stdc++.h>
using 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,y2;
    scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
    if (x1 == x2) {
      if (y1 > y2) swap(y1,y2);
      a[++n1] = node1{x1,y2};
    } else {
      if (x1 > x2) swap(x1,x2);
      b[++n2] = node2{x1,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;
}