[Baekjoon - 3411] Jewel heist

난이도: Platinum I

 

태그

• Sweeping
• Segment Tree
• TreeSet
• Coordinate Compression

 

풀이

1. 모든 색깔을 가지지 않는 확실한 방법은?

어떤 하나의 색깔을 고의적으로 피한다면, 적어도 그 색깔을 가지지 않을 것임은 분명하니

모든 색깔을 가지지 않을 수 있습니다.

 

2. 특정 색깔을 가지지 않겠다고 해보자. 그럼, 가져갈 수 있는 개수의 최댓값은?

그 색깔을 가지고 있는 점의 위치를 \( (y_1, x_1), (y_2, x_2), \ldots, (y_N, x_N) \)이라고 해봅시다.

또한, \( y_1 \le y_2 \le \ldots y_N \)이라고 해봅시다.

 

이제 저희가 설치할 Robotic Hand의 \( y \)를 천천히 늘려나가봅시다.

충분히 작은 \( y \)값에 대해서는, 고려해야 할 점이 없으므로 구간 전체에 설치할 수 있습니다.

// 엄밀히는 \( y < y_1 \)인 동안을 의미합니다.

 

그러다가, \( y = y_1 \)이 되었다고 해봅시다.

그 때부터는 \( x_1 \)을 포함시킨 구간으로는 설치할 수 없기 때문에, \( (-\infty, x_1) \)로 설치하는 경우와 \( (x_1, \infty) \)로 설치하는 경우 2가지로 나뉘게 됩니다.

이 이후로도 \( y \)를 올려가면서 새로운 점을 만날 때마다, 하나의 구간이 2개로 나뉘게 되겠죠.

 

이렇게 하면 경우가 너무 많아지지 않을까 걱정하게 될 수도 있습니다.

하지만, 하나의 점은 최대 2개의 구간만을 새로 만들어내므로, 총 구간 개수는 \( O(N) \)이 됩니다.

 

3. [2]를 모든 색깔에 대해 돌리는 건 느릴텐데, 더 빠르게 할 수 있을까?

색깔을 하나씩 돌릴 필요는 없습니다.

\( y \)를 늘려나가면서 [2]를 적용하는 과정을 모든 색깔에 대해 병렬적으로 처리할 수 있기 때문이죠.

 

모든 색깔에 대해 병렬적으로 처리를 하게 된다면, 스위핑을 1번만 해주면 되니 충분히 빠른 시간에 답을 구할 수 있게 됩니다.

 

4. 코드

const int N = 262144;
int seg[524290];
void upd(int pos, int val){ pos += N-1;
    seg[pos] += val; pos >>= 1;
    while (pos){ seg[pos] = seg[pos<<1] + seg[pos<<1|1]; pos >>= 1; }
}
int qry(int st, int ed){ st += N-1; ed += N-1;
    int res = 0;
    while (st <= ed){
        if (st&1){ res += seg[st]; st++; }
        if (~ed&1){ res += seg[ed]; ed--; }
        if (st > ed){ break; } st >>= 1; ed >>= 1;
    }
    return res;
}
 
pi3 arr[200020];
vector<int> cs;
inline int cvt(int x){ return lower_bound(all(cs), x)-cs.begin() + 1; }
 
set<pi2> qrr[200020];
 
void Main(){
    int t; cin >> t; while (t--){
        int n, m; cin >> n >> m;
        for (int i = 1; i <= n; i++){
            cin >> arr[i].fr.sc >> arr[i].fr.fr >> arr[i].sc;
            cs.push_back(arr[i].fr.sc);
        }
        unq(cs); for (int i = 1; i <= n; i++){ arr[i].fr.sc = cvt(arr[i].fr.sc); }
        for (int i = 1; i <= m; i++){ qrr[i].insert({1, cs.size()}); }
        sort(arr+1, arr+n+1);
        int ans = 0;
        int i1 = 1; while (i1 <= n){
            int i2 = i1; while (i2 <= n){
                if (arr[i1].fr.fr == arr[i2].fr.fr){ i2++; } else{ break; }
            }
            for (int i = i1; i < i2; i++){
                int x = arr[i].fr.sc, c = arr[i].sc;
                //cout << "POS " << arr[i1].fr.fr << "   " << x << ' ' << c << endl;
                auto it = qrr[c].upper_bound({x, N});
                if (it == qrr[c].begin()){ continue; } it = prev(it);
                pi2 p = *it; if (p.fr > x || x > p.sc){ continue; }
                //cout << "QRY " << p.fr << ' ' << p.sc << "   " << qry(p.fr, p.sc) << endl;
                ans = max(ans, qry(p.fr, p.sc));
                qrr[c].erase(it);
                if (p.fr < x){ qrr[c].insert({p.fr, x-1}); }
                if (x < p.sc){ qrr[c].insert({x+1, p.sc}); }
            }
            for (int i = i1; i < i2; i++){ upd(arr[i].fr.sc, +1); }
            i1 = i2; //cout << endl;
        }
        for (int i = 1; i <= m; i++){
            for (pi2 p : qrr[i]){
                //cout << "QRY " << p.fr << ' ' << p.sc << "   " << qry(p.fr, p.sc) << endl;
                ans = max(ans, qry(p.fr, p.sc));
            }
        }
        cout << ans << endl;
        cs.clear(); for (int i = 1; i <= m; i++){ qrr[i].clear(); }
        for (int i = 1; i < N+N; i++){ seg[i] = 0; }
    }
}