BOJ 26399 - Lampice

BOJ 26399 - Lampice

$n \le 150$ 이기 때문에 뭔가 이걸로 잘 해볼만하다.

금광세그문제를 생각해보면 $O(n^2)$ 으로 무언가 완전탐색하지 않았는가

그래서 시간복잡도를 $O(n^2m)$ 정도로 생각해볼 수 있다.

이제 여기서 행 두개를 고정해두고 열들을 뭘로 스위핑을 할거냐가 문젠데, 여기서 세그먼트 트리를 쓰려다가 도저히 안되어서 태그를 깠다.

정해는 XOR해싱이다.

XOR해싱은 저번에 코포에서 꽤나 어려운 문제에서 한번 접해보고 다시 만날일은 없었는데 여기서 만날줄 몰랐다.

어쨌든 여기서 XOR해싱을 떠올릴 수 있는 직관은 두개다 포함되거나 두개다 포함안되는것이 $x \oplus x=0,~0=0$ 인 성질과 동치이기 때문이리라.

모든 램프에 $1 \to 2^{60}$ 정도의 랜덤값을 할당한다.

어쨌든 위 아이디어들과 prefix sum으로 빠르게 세줄 수 있다.

$l \sim r$ 까지 $\oplus$한 것은, $0 \sim r$ 까지 $xor$ 한것에서 $0 \sim l-1$ 까지 $\oplus$한 것과 $\oplus$ 한 것이기 때문이다.

즉, prefix sum에서 $\oplus$값이 같은것의 pair 수만 세주면 된다.

단, 직사각형의 넓이가 $0$이 되지 않게 최소 행과 열이 $1$씩은 차이나게만 세줌에 유의하라.

struct _random {  
   mt19937 gen;  
   _random() : gen((unsigned) chrono::steady_clock::now().time_since_epoch().count()) {}  
   template<class T = int>  
   T nextInt(T l = 0, T r = 32767) { return uniform_int_distribution<T>(l, r)(gen); }  
   double nextDouble(double l = 0, double r = 1) { return uniform_real_distribution<double>(l, r)(gen); }  
} rd;  
  
void solve() {  
   int Y, X, K;  
   cin >> Y >> X >> K;  
   vector<vector<array<int, 3>>> row(Y + 1);  
   vi H(K);  
   for (int i = 0; i < K; i++) H[i] = rd.nextInt<int>(0, 2e15);  
   for (int i = 0; i < K; i++) {  
      int y1, x1, y2, x2;  
      cin >> y1 >> x1 >> y2 >> x2;  
      if (y1 == y2 && x1 == x2) continue;  
      if (x1 > x2) swap(y1, y2), swap(x1, x2);  
      row[y1].pb({x1, i, H[i]});  
      row[y2].pb({x2, i, H[i]});  
   }  
  
   for (int y = 0; y <= Y; y++) sort(all(row[y]));  
  
   ll ans = 0;  
   for (int y1 = 0; y1 < Y; y1++) {  
      vi psum(X + 2);  
      for (int y2 = y1; y2 <= Y; y2++) {  
         vi add(X + 2);  
         for (auto &[x, color, hv]: row[y2]) add[x] ^= hv;  
  
         for (int i = 1; i <= X; i++) add[i] ^= add[i - 1];  
         for (int i = 0; i <= X; i++) psum[i] ^= add[i];  
  
         if (y1 == y2) continue;  
         unordered_map<int, int> cnt;  
         cnt[0] = 1;  
         for (int i = 1; i <= X; i++) {  
            ans += cnt[psum[i]];  
            cnt[psum[i - 1]]++;  
         }  
      }  
   }  
   cout << ans;  
}