imos - 누적 화법

AOJ 0531 Paint Color 를 풀 때 누적 과 묘 용 인 imos 법 을 배 웠 습 니 다. 원문 은 일본어 이기 때문에 특별히 번역 해 왔 습 니 다.특히 저자 켄 타 로 이마 조 는 나 와 동갑 인 데 도 이렇게 많은 성 과 를 거 두 었 는데 도 나 는 아무것도 이 루 지 못 해 부끄럽다.
imos 법
imos 법 은 누적 과 알고리즘 을 여러 번 원, 고 차 공간 으로 확대 하 는 방법 이다.프로그램 경연 대회 에 서 는 최대 2 차원 1 회 에 불과 한 문 제 를 냈 지만 2012 년 켄 타 로 이마 조 는 고 차원 고 차원 공간 에 활용 해 신호 처리 / 이미지 처리 분야 에서 성 과 를 거 뒀 다.
기초 imos 법
가장 간단 한 imos 법 은 1 차원 0 차 계수 의 구 해 사상 이다.그림 에서 보 듯 이 세 개의 러시아 사각형 이 함께 있 으 면 허공 에 떠 있 는 부분 이 떨 어 지고 왼쪽 에서 오른쪽 높이 를 구 합 니까?이 높이 는 가로 좌표 가 고정 되 었 을 때 위의 사각형 높이 의 합 이다.이것 이 가장 간단 한 imos 법 이다.
예제
당신 은 카페 를 운영 하고 있 습 니 다. 당신 의 카페 에는 모든 손님 이 S 에 있 습 니 다.i 시시각각 입장, E시시각각 출점 하 다.구점 에는 최대 몇 명의 손님 이 있 습 니까?(손님 은 최대 C 개, 항상 T 내 에 있 습 니 다. 여러 명 이 동시에 가게 에 들 어가 면 먼저 가게 에 나 온 사람 을 계산 합 니 다).
소박 한 해법
소박 한 사상 은 매 순간 고객 의 수 를 계산 해 최대 치 를 찾 는 것 이다.하지만 복잡 도 는 O (CT) 다. 

#include 
#include 
using namespace std;
 
#define C 4
#define T 10
//          
int S[C] = { 1, 3, 5, 7 };
//          
int E[C] = { 2, 8, 6, 8 };
//      
int table[T];
 
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	memset(table, 0, sizeof(table));
	for (int i = 0; i < C; i++) 
	{
		//     S[i]   E[i] - 1         
		for (int j = S[i]; j < E[i]; j++) 
		{
			table[j]++;
		}
	}
	//     
	cout << *max_element(table, table + T) << endl;
	system("pause");
	return 0;
}

imos 법 해법 imos 법의 기본 방향 은 출입 점 시간의 인원 변화 만 집계 하 는 것 이다.최종 통 계 를 할 때 매 순간 에 전 시간의 통 계량 (저 는 개인 적 으로 포 인 트 를 구 하 는 것 과 같다) 을 더 해 야 합 니 다. 그 중에서 가장 큰 가 치 는 바로 원 하 는 것 입 니 다.복잡 도 O (C) 를 기록 하고 복잡 도 O (T) 를 누적 하기 때문에 전체적인 복잡 도 O (C + T).

#include 
#include 
using namespace std;
 
#define C 4
#define T 10
//          
int S[C] = { 1, 3, 5, 7 };
//          
int E[C] = { 2, 8, 6, 8 };
//      
int table[T];
 
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	memset(table, 0, sizeof(table));
	for (int i = 0; i < C; i++) 
	{
		table[S[i]]++;  //   +1
		table[E[i]]--;  //   -1
	}
	//   
	for (int i = 1; i < T; i++) 
	{
		table[i] += table[i - 1];
	}
	//     
	cout << *max_element(table, table + T) << endl;
	system("pause");
	return 0;
}

2 차원 까지 보급 하 다
imos 는 소박 한 방법 에 비해 차원 이 커지 면서 복잡 도가 낮 아 지 는 것 이 장점 이다.
예제
당신 은 몬스터 를 잡 는 게임 을 하고 있 습 니 다. 지금 당신 앞 에는 W * H 의 지도 가 있 습 니 다. 지도 에는 N 종의 괴물 이 있 습 니 다.몬스터 i 는 왼쪽 아래 (B i, C i), 오른쪽 위 (A i, D i) 의 사각형 영역 에서 만 나타 납 니 다.단위 구역 내 최대 몇 종류의 몬스터 가 있 습 니까?
 
소박 한 해법
소박 한 해법 은 각 단위 구역 에 나타 나 는 몬스터 수 를 계산 해 최대 치 를 찾 는 것 이다.복잡 도 는 O (NWH) 다.

#include 
#include 
using namespace std;
#define  W  6
#define  H  6
#define  N  4
//      
int B[N] = {3,4,3,5,};
int C[N] = {0,1,2,2,};
//      
int A[N] = {0,3,2,2,};
int D[N] = {3,2,3,5,};
//         
int tiles[H][W];
 
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	memset(tiles, 0, sizeof(tiles));
	for (int i = 0; i < N; i++) 
	{
		//    i       [(A[i],C[i]), (B[i],D[i]))       
		for (int y = C[i]; y < D[i]; y++) 
		{
			for (int x = A[i]; x < B[i]; x++) 
			{
				tiles[y][x]++;
			}
		}
	}
	//     
	cout << *max_element(tiles[0], tiles[0] + H * W) << endl;
	system("pause");
	return 0;
}

imos 법 해법
사각형 의 왼쪽 상단 (A [i], C [i]) +1, 오른쪽 상단 (A [i], D [i]) − 1, 왼쪽 하단 (B [i], C [i]) − 1, 오른쪽 하단 (B [i], D [i]) + 1 로 최종 결 과 를 집계 하기 전에 누적 된다.더하기 1 빼 기 1 O (N), 누적 (WH) 전체 복잡 도 O (N + WH) 。

#include 
#include 
using namespace std;
#define  W  6
#define  H  6
#define  N  4
//      
int B[N] = {3,4,3,5,};
int C[N] = {0,1,2,2,};
//      
int A[N] = {0,3,2,2,};
int D[N] = {3,2,3,5,};
//         
int tiles[H][W];
 
///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
	memset(tiles, 0, sizeof(tiles));
	//       (  3)
	for (int i = 0; i < N; i++) 
	{
		tiles[C[i]][A[i]]++;
		tiles[C[i]][B[i]]--;
		tiles[D[i]][A[i]]--;
		tiles[D[i]][B[i]]++;
	}
	//       (  4, 5)
	for (int y = 0; y < H; y++) 
	{
		for (int x = 1; x < W; x++) 
		{
			tiles[y][x] += tiles[y][x - 1];
		}
	}
	//       (  6, 7)
	for (int y = 1; y < H; y++) 
	{
		for (int x = 0; x < W; x++) 
		{
			tiles[y][x] += tiles[y - 1][x];
		}
	}
 
	cout << *max_element(tiles[0], tiles[0] + H * W) << endl;
	system("pause");
	return 0;
}

그림 3: 영향력 계산
그림 4: 가로 누적
그림 5: 가로 누적 결과
그림 6: 세로 누적
그림 7: 세로 누적 결과
더 높 은 용법
잠시 사용 할 수 없습니다. 주 소 를 기록 하고 시간 이 있 으 면 다시 보 세 요.
Reference
http://imoz.jp/algorithms/imos_method.html
전환 하 다http://www.hankcs.com/program/algorithm/imos_method.html