백준 11012 (C++) Egg

최초 업로드: 2025-04-23 13:30:44

최근 수정 시간: 2025-07-25 09:16:02

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] Egg

#### [문제 링크](https://www.acmicpc.net/problem/11012)

## 문제 설명

You are a president deeply loved by many folks in your country. Every time you go on a parade (which is your main job, what else should a president do), the folks would throw eggs at you — because you love eggs! The folks passionately send their eggs to you, and you always can catch the eggs. In fact, egg-catching is exactly what makes you look forward to the parade every day! A folk would throw an egg at you for each time your parade comes to his home. You are given n coordinates on a 2D-map, these are where the folks that will throw an egg at you each time they see you on a parade. Note that the coordinates may repeat, since several folks may live together. There are in total m days left in your term and the area to parade each day are set. A parade always takes place in an axis-parallel rectangle area, as stated clearly in the constitution and as the president you have no choice but to follow it. You are given m 2D-ranges [ℓ, r]×[b, t] describing the parades.

## 입력

Input begins with an integer T (1 ≤ T ≤ 20) indicating the number of test cases. The first line of each test case contains two integers n (0 < n ≤ 10000) and m (0 ≤ m ≤ 50000) separated by a blank where n is the number of folks throwing eggs and m is the number of days left in your term. Each of the following n lines contains two integers x and y (0 ≤ x, y ≤ 105) indicating that there is a folk’s home located at (x, y). Then m more lines follow. Each of them contains four integer ℓ, r, b, t (0 ≤ ℓ ≤ r ≤ 105, 0 ≤ b ≤ t ≤ 105) separated by blanks. [ℓ, r] × [b, t] corresponds to a parade area.

## 출력

For each test case, output the total sum of eggs you receive on one line.

## 풀이
#### x를 기준으로 정렬하여 스위핑을 진행하면 된다. 사각형 y좌표 범위를 세그먼트 트리로 범위를 기록하다 사람들의 집 위치가 겹치는 만큼 더해주면 된다.

``` c++
#include<bits/stdc++.h>
using namespace std;

const int MAX = 100'000;

int _size=1, arr[MAX*4], lazy[MAX*4];

struct egg {
    int x, y;
};

struct rect {
    int x, y1, y2, val;
};

void updateLazy(int nodeNum, int nodeL, int nodeR) {
    if(lazy[nodeNum]) {
        arr[nodeNum] += lazy[nodeNum];
        if(nodeL!=nodeR) {
            lazy[nodeNum*2] += lazy[nodeNum];
            lazy[nodeNum*2+1] += lazy[nodeNum];
        }
        lazy[nodeNum]=0;
    }
}

void updateRange(int L, int R, int nodeNum, int nodeL, int nodeR, int val) {
 if(R<nodeL || nodeR<L) return;
 if(L<=nodeL && nodeR<=R) {
 lazy[nodeNum] += val;
 return;
 }
 int mid = (nodeL+nodeR)/2;
 updateRange(L, R, nodeNum*2, nodeL, mid, val);
 updateRange(L, R, nodeNum*2+1, mid+1, nodeR, val);
}

int search(int L, int R, int nodeNum=1, int nodeL=0, int nodeR=_size/2-1) {
 updateLazy(nodeNum, nodeL, nodeR);
 if(R<nodeL || nodeR<L) return 0;
 if(L<=nodeL && nodeR<=R) return arr[nodeNum];
 int mid = (nodeL+nodeR)/2;
 return search(L, R, nodeNum*2, nodeL, mid) + search(L, R, nodeNum*2+1, mid+1, nodeR);
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 while(_size<MAX) _size<<=1;
 _size<<=1;

int t; cin >> t;
 while(t--) {
 int n, m; cin >> n >> m;
 vector<egg> eggs(n);
 for(int i=0;i<n;i++) cin >> eggs[i].x >> eggs[i].y;
 sort(eggs.begin(), eggs.end(), [](egg a, egg b) { return a.x < b.x; });

vector<rect> rects;
 for(int i=0;i<m;i++) {
 int x1, x2, y1, y2; cin >> x1 >> x2 >> y1 >> y2;
 rects.push_back({x1, y1, y2, 1});
 rects.push_back({x2+1, y1, y2, -1});
 }
 sort(rects.begin(), rects.end(), [](rect a, rect b) { return a.x < b.x; });

int eggIdx=0, total=0;
 for(rect r : rects) {
 while(eggIdx<n && eggs[eggIdx].x<r.x) {
 total += search(eggs[eggIdx].y, eggs[eggIdx].y);
 eggIdx++;
 }
 updateRange(r.y1, r.y2, 1, 0, _size/2-1, r.val);
 }
 cout << total << '\n';
 }
}
```