E. Marbles

빨강, 파랑, 초록색, 세 가지 색상의 공들이 2차원 평면에 배치 되어 있다. 빨간색 공을 세는 직사각형, 파란색 공을 세는 직사각형, 초록색 공을 세는 직사각형 세 개를 크기 제한 없이 겹치지 않게 잡았을 때 세어지는 공의 개수를 최대화 하는 문제다. 여기서 직사각형 변 위에 있는 공도 세어주고, 겹쳐서는 안된다.

우선 직사각형의 크기 제한이 없다는 점을 생각하자. 그러면 가능한 직사각형의 배치를 아래와 같이 크게 두 가지로 나눌 수 있다.

        

이 두 가지 경우에 대한 코딩을 하고 y축 대칭, 직선 y=x에 대한 선대칭 및 $3! = 6$가지의 색상 재배열등을 행해 모든 경우를 고려할 수 있다.

우선 각 점들을 x 좌표 기준으로 정렬을 한 뒤 빨간색 영역이 차지하는 범위를 정한 뒤 segment tree 자료구조를 이용해 파란색과 초록색 영역이 적절히 나눠졌을 때 최대값을 구한다. 기본적인 아이디어는 초록색 점에게 1의 가중치를 주고, 파란색 점에게 -1의 가중치를 주어, 파란색 점의 개수를 미리 세주고 최대의 가중치를 포함하는 영역을 구하는 방법이다.

자료구조에서 점의 위치를 2차원이 아닌 1차원으로 표현할 수 있고, 각 좌표에 가중치를 더하는 작업이 $O(\lg N)$, 영역이 갖는 최대 가중치 값을 $O(1)$에 계산할 수 있다. 영역은 1차원 좌표계의 중간이 아니라 처음과 중간 지점까지 연속한 영역을 고려하면 되므로 최대 가중치 값을 찾는 작업이 $O(1)$에 수행될 수 있다.

#include <stdio.h> #include <vector> #include <algorithm> using namespace std; #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() int T, ans; int XS, YS; struct Z{ Z(int x=0, int y=0): x(x), y(y){} int x, y; bool operator < (const Z &ot)const{ return x < ot.x; } }; typedef vector<Z> points; struct NODE{ int sum, maxpre; NODE *left, *right; } container[99999]; int IDX; NODE *new_node() { NODE *ret = &container[IDX++]; ret->sum = ret->maxpre = 0; ret->left = ret->right = NULL; return ret; } void add_val(NODE *now, int s, int e, int t, int v) { if (e < t || s > t) return; if (s == e){ now->sum += v; now->maxpre = max(0, now->sum); return; } if (!now->left) now->left = new_node(), now->right = new_node(); int m = (s+e)>>1; add_val(now->left, s, m, t, v); add_val(now->right, m+1, e, t, v); now->sum = now->left->sum + now->right->sum; now->maxpre = max(now->left->maxpre, now->left->sum + now->right->maxpre); } void case1(points &R, points &G, points &B) { int N = sz(R), M = sz(G), K = sz(B); int p = 0, q = 0, r = 0; int val = 0, i; IDX = 0; NODE *root = new_node(); for (i=0;i<M;i++) add_val(root, 1, XS, G[i].x, 1); for (i=0;i<K;i++) add_val(root, 1, XS, B[i].x, -1), val++; for (;p<N;p++){ val++; if (p+1 < N && R[p].x == R[p+1].x) continue; while (q < M && G[q].x <= R[p].x){ add_val(root, 1, XS, G[q].x, -1); q++; } while (r < K && B[r].x <= R[p].x){ add_val(root, 1, XS, B[r].x, 1); val--; r++; } if (ans < val + root->maxpre) ans = val + root->maxpre; } } void case2(points &R, points &G, points &B) { int N = sz(R), M = sz(G), K = sz(B); int p = 0, q = 0, r = 0; int val = 0, i; IDX = 0; NODE *root = new_node(); for (i=0;i<M;i++) add_val(root, 1, YS, G[i].y, 1); for (i=0;i<K;i++) add_val(root, 1, YS, B[i].y, -1), val++; for (;p<N;p++){ val++; if (p+1 < N && R[p].x == R[p+1].x) continue; while (q < M && G[q].x <= R[p].x){ add_val(root, 1, YS, G[q].y, -1); q++; } while (r < K && B[r].x <= R[p].x){ add_val(root, 1, YS, B[r].y, 1); val--; r++; } if (ans < val + root->maxpre) ans = val + root->maxpre; } } void proc_one_color(points &R, points &G, points &B, int skip) { if (!skip) case1(R, G, B); case2(R, G, B); } void proc_all_color(points &R, points &G, points &B, int skip) { sort(all(R)); sort(all(G)); sort(all(B)); proc_one_color(R, G, B, skip); proc_one_color(R, B, G, skip); proc_one_color(G, R, B, skip); proc_one_color(G, B, R, skip); proc_one_color(B, R, G, skip); proc_one_color(B, G, R, skip); } int main() { int i, j; for (scanf("%d", &T);T--;){ points R, G, B; vector <int> XX, YY; int n, m, k; scanf("%d%d%d", &n, &m, &k); while (n--){ scanf("%d%d", &i, &j); XX.push_back(i); YY.push_back(j); R.emplace_back(i, j); } while (m--){ scanf("%d%d", &i, &j); XX.push_back(i); YY.push_back(j); G.emplace_back(i, j); } while (k--){ scanf("%d%d", &i, &j); XX.push_back(i); YY.push_back(j); B.emplace_back(i, j); } sort(all(XX)); XX.erase(unique(all(XX)), XX.end()); sort(all(YY)); YY.erase(unique(all(YY)), YY.end()); XS = sz(XX); YS = sz(YY); for (Z &p: R){ p.x = lower_bound(all(XX), p.x) - XX.begin() + 1; p.y = lower_bound(all(YY), p.y) - YY.begin() + 1; } for (Z &p: G){ p.x = lower_bound(all(XX), p.x) - XX.begin() + 1; p.y = lower_bound(all(YY), p.y) - YY.begin() + 1; } for (Z &p: B){ p.x = lower_bound(all(XX), p.x) - XX.begin() + 1; p.y = lower_bound(all(YY), p.y) - YY.begin() + 1; } ans = 0; proc_all_color(R, G, B, 0); for (Z &p: R) p.x = XS-p.x+1; for (Z &p: G) p.x = XS-p.x+1; for (Z &p: B) p.x = XS-p.x+1; proc_all_color(R, G, B, 1); for (Z &p: R) swap(p.x, p.y); for (Z &p: G) swap(p.x, p.y); for (Z &p: B) swap(p.x, p.y); swap(XS, YS); proc_all_color(R, G, B, 0); for (Z &p: R) p.x = XS-p.x+1; for (Z &p: G) p.x = XS-p.x+1; for (Z &p: B) p.x = XS-p.x+1; proc_all_color(R, G, B, 1); printf("%d\n", ans); } }