http://boj.kr/1a57ae879f1f4dceb6798385c7fa6de0
y방향으로 훑으면서 계란을 얻어맞는 x 범위를 펜윅으로 가져오는 전략 채택
사각형 하나 얻을 때마다 해당 사각형에 포함되는 좌표들을 가져옴
모두 가져왔으면 tmp에 펜윅 구간 합을 더함
그리고 현재 좌표 축에서 벗어나는 사각형을 하나씩 제함
제할 때마다 tmp에 펜윅 구간 합 결과를 빼고 해당 사각형에 포함되는 점들을 제거함
이렇게 다 좌표 돌아서 ans = max(ans, tmp)가 답
인데 50% 찍자마자 바로 주금
구글링하면 PST만 있고 스위핑은 하나도 안 보여...
사각형이 아니라 두 변을 event로 넣어야함 아니면 tle날걸
이거 PST 안쓰는 내 풀이는 이럼. 1) 계란 점과 사각형의 양변을 모두 똑같은 컨테이너에 넣고, 정렬한다. 2) 정렬은 x축 (아니면 y축하든가) 으로 하되, x축값이 같은 경우 사각형의 왼쪽 변 - 계란 점 - 사각형의 오른쪽 변 순으로 정렬한다.
3) 쭉 스위핑한다. 세그트리는 y좌표로 관리된다. 계란 점이면 세그 y좌표에 1을 더한다. 왼쪽 변일 경우, 이게 i번째 사각형이면 A[i] = 세그트리.get(y_low, y_high) 로 세팅 한다. 오른쪽 변일 경우, 쿼리의 답은 세그트리.get(y_low, y_high) - A[i]
메모이제이션이 필요한 거였네... 정말 고마워
아..........같이 정렬...이란 방법