Gym 100733 J Summer Wars 문제 풀이: 스캐닝 라인 을 활용 한 사상

제목:
n 개의 점, m 개의 가로 선 을 드 리 겠 습 니 다.너 는 이 선분 들 을 가로로 옮 길 수 있 지만, 이 선분 들 의 상대 적 인 위 치 는 바 꿀 수 없다.만약 에 한 점 이 그의 바로 위 와 바로 아래 에 모두 선분 (선분 의 종점 포함) 이 있다 면 이 점 은 '차단' 으로 간주 되 고 임 의 평 이 를 통 해 우리 가 가장 많은 점 을 가 릴 수 있 는 수량 을 물 었 다.
문제 풀이 방향:
먼저 모든 점 을 오른쪽으로 1000000 개의 단 위 를 평평 하 게 옮 긴 다음 에 그 선분 의 위치 가 변 하지 않 고 우 리 는 이 점 들 을 평평 하 게 옮 기기 시작 했다. 그러면 우 리 는 점 이 왼쪽으로 이동 하 는 거 리 는 반드시 양수 이 고 편리 하 게 처리 할 것 을 보증한다.
이렇게 해서 우 리 는 각 점 에서 왼쪽으로 이동 하 는 거 리 를 구 한 후에 문제 조건 을 만족 시 킬 수 있 는 집합 W 를 구 한 다음 에 특정한 거리 값 이 모든 집합 에서 가장 많은 횟수 를 나타 내 면 된다. 이 횟수 가 바로 답 이다.
우리 의 중점 은 이 집합 W 를 구 하 는 것 이다.만약 에 폭력 적 으로 찾 으 면 제목 의 데이터 범 위 는 1000000 이 고 포인트 가 1000 이 며 이들 의 상승 복잡 도 는 분명 불가능 하 다. 여기 서 우 리 는 스캐닝 라인 의 사상 을 활용 해 야 한다.
우 리 는 한 라인 을 두 개의 점 으로 본다. 입 점 과 출 점 이다.
예 를 들 어 (x1, y) - (x2, y) 의 선분 을 우 리 는 (x1, y) 의 위치 에 1 을 표시 하고 (x2 + 1, y) 의 위치 에 1 을 표시 한 다음 에 가로 좌표 에 따라 왼쪽 에서 오른쪽으로 이 점 들 을 훑 어 보 았 다. 사실은 선 을 스 캔 하 는 사상 이다. 그리고 실행 가능 한 범위 내 에서 우리 의 P 배열 위 치 를 + 1 한 다음 에 P 중의 최대 치 를 찾 으 면 된다.
여기 서 P 배열 을 업데이트 할 때 우 리 는 직접 폭력 적 으로 업데이트 할 수 없습니다. 예 를 들 어 우 리 는 구간 [l, r] 구간 을 모두 + 1 로 업데이트 하려 고 합 니 다. 우 리 는 P [l] 위치 에서 + 1, P [r + 1] 위치 에서 - 1 을 업데이트 한 다음 에 마지막 에 같이 업데이트 하면 됩 니 다.
코드 는 다음 과 같 습 니 다:

#include <bits/stdc++.h>

using namespace std;

int N, M;
pair<int, int> A[1000]; //      

struct event {	//         ，tp = 1     ，tp = -1     
	int x, y, tp;
	bool operator< (const event& other) const {
		return x < other.x;
	}
};

event B[2015];
int P[2000016];	//       

int main() {
	//freopen("in.in", "r", stdin);
	//freopen("out.out", "w", stdout);
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%d%d", &A[i].second, &A[i].first);	//     ，   y，x       
		A[i].first += 1000000;
	}
	int y, x1, x2;
	for (int i = 0; i < M; i++) {
		scanf("%d%d%d", &y, &x1, &x2);
		B[i * 2] = (event) {x1, y, 1};
		B[i * 2 + 1] = (event) {x2 + 1, y, -1};
	}
	sort(B, B + 2 * M);		//                     
	multiset<int> s; s.clear();		//s                 
	for (int i = 0; i < N; i++) {
		int last = -1;
		for (int j = 0, k; j < 2 * M; j = k) {
			for (k = j; k < 2 * M && B[k].x == B[j].x; k++) {
				if (B[k].tp == -1)
					s.erase(s.find(B[k].y));
				else
					s.insert(B[k].y);
			}
			if (last != -1) P[A[i].first - B[j].x + 1]++, P[A[i].first - last + 1]--;		//O（1）  P  

			if (s.empty() || *s.begin() > A[i].second || *s.rbegin() < A[i].second)	//         i        
				last = -1;
			else
				last = B[j].x;		//          
		}
	}
	int ans = 0;
	for (int i = 1; i <= 2000015; i++)
		ans = max(ans, P[i] += P[i - 1]);	//             ，    
	printf("%d
", ans);
	return 0;
}