By Standing On The Shoulders Of Giants

www.acmicpc.net/problem/17408

그럴 수 밖에 없는 Idea

쿼리 : 100,000 <-- 대표적인 세그먼트트리 문제일 때의 쿼리 수

자주 바꿀 수 있다 <-- 세그먼트트리의 가능성

최댓값을 출력 <-- 세그먼트트리의 가능성

최솟값으로 떠올릴 수 있는 알고리즘

- 완전탐색

- 이분탐색

- 세그먼트트리

풀이

1.  l ≤ i < j ≤ r을 만족하는 모든 Ai + Aj 중에서 최댓값

쉽게 생각하면 쉽고 어렵게 생각하면 어려워질 수 있다.

[l,r] 사이 두 수의 합의 최대값을 고른다고 할 때 

먼저 떠오를 수 있는 것

1. 완전탐색 : $nC_2$

이어서 2차원 세그먼트트리를 구현해야하나 싶지만

2. 두 수의 합의 최대값 = 첫번째 최대값 + 두번째 최대값

첫번째 최대값 : 세그먼트트리 최대값

두번째 최대값 : 최대값을 제외한 양 옆구간

$2logN$ 으로 구할 수 있다. 

시간복잡도 : $M*(2logN)$

쿼리 : $M$

두 수의 합의 최대값 : 첫번째 최대값 + 두번째 최대값 = $2logN$

update : $logN$

#include<stdio.h>
#define Max 100000
typedef struct node {
	int idx;
	int num;
}Node;
int SHIFT = 1;
Node segTree[Max * 4];
int N, M;
 
void makeSHIFT() {
	while (SHIFT < N)
		SHIFT <<= 1;
	SHIFT -= 1;
}
 
void update(int dataIdx, int diff) {
	int nodeIdx = dataIdx + SHIFT; //주의1.leaf 에는 값을 직접 넣음
	segTree[nodeIdx].num = diff;
	segTree[nodeIdx].idx = dataIdx;
 
	while (nodeIdx > 1) { //주의2.nodeIdx는 parent 역할
		nodeIdx >>= 1;
		int childLeft = nodeIdx * 2;
		int childRight = nodeIdx * 2 + 1;
		segTree[nodeIdx] = segTree[childLeft].num > segTree[childRight].num ? segTree[childLeft] : segTree[childRight];
	}
}
 
Node query(int dataLeft, int dataRight) {
	int nodeLeft = dataLeft + SHIFT;
	int nodeRight = dataRight + SHIFT;
 
	Node max = { 0,0 };
	while (nodeLeft < nodeRight) {
		if (nodeLeft % 2) {
			max = max.num > segTree[nodeLeft].num ? max : segTree[nodeLeft];
			nodeLeft += 1;
			nodeLeft >>= 1;
		}
		else
			nodeLeft >>= 1;
 
		if (nodeRight % 2)
			nodeRight >>= 1;
		else {
			max = max.num > segTree[nodeRight].num ? max : segTree[nodeRight];
			nodeRight -= 1;
			nodeRight >>= 1;
		}
	}
 
	if (nodeLeft == nodeRight)
		max = max.num > segTree[nodeLeft].num ? max : segTree[nodeLeft];
 
	return max;
}
int main() {
	scanf("%d", &N);
	makeSHIFT();
 
	for (int i = 1; i <= N; i++) {
		int n;
		scanf("%d", &n);
		update(i, n);
	}
 
	scanf("%d", &M);
	while (M--) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		if (a == 1)
			update(b, c);
		else {
			Node max1 = query(b, c);
			Node max2_1 = query(b, max1.idx - 1);
			Node max2_2 = query(max1.idx + 1, c);
			int res = (max1.num + max2_1.num) > (max1.num + max2_2.num) ? (max1.num + max2_1.num) : (max1.num + max2_2.num);
			printf("%d\n", res);
		}
	}
	return 0;
}

주의

1. 세그먼트트리의 최소값 최대값 update 시 :

 - leaf에는 값을 직접 넣는다.

 - update 시 nodeIdx 는 parent로써 역할을 하므로 반복 조건은 nodeIdx > 1 이다.

 - 최소값을 구할경우 전체 값에 대해 Max 업데이트를 해야한다.

그럴 수 밖에 없는 Idea

아.. 이거 하나하나 확인해서 되는 것 중에 젤 작은 값으로 최솟값을 찾을 수 있지 않을까?

--> 답에 과정을 끼워 맞추는 방법

이 분 탐 색!

예제 

심사대 2개 : 7초 10초

6명

에 대해 그림과 같이 배분해보면 순서가 있는 양 설명한 것은 속임수임을 알 수 있다.

최솟값으로 떠올릴 수 있는 알고리즘

- 완전탐색

- 이분탐색

- ???

풀이

1. 이분탐색 대상 : 심사완료시간

2. check 함수 : 시간안에 주어진 사람들을 모두 심사할 수 있나?

2. check 함수

 마치 순서를 필요로 하는 것 같지만 시간을 정해놓고 이 시간안에 심사대의 심사한 사람 수를 다 더하여 조건과 같으면 된다.

mid 값을 만족하면 시간은 줄여나가야한다. --> 최소값 문제, right=mid-1 로 줄임

cf) 최대값 문제, 시간을 늘려야 한다. left=mid+1

#include<stdio.h>
#define Max 1000000000000000000
unsigned long long N, M;
long long time[1000001];
 
int check(long long mid) {
	unsigned long long val = 0;
	for (int i = 0; i < N; i++)
		val += (mid / time[i]);
	return M > val ? 0 : 1;
 
}
 
long long binarysearch(long long left, long long right) {
	long long ans = Max;
	while (left <= right) {
		long long mid = left + (right - left) / 2;
		if (check(mid)) {
			ans = ans < mid ? ans : mid;
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}
	return ans;
}
 
int main() {
	scanf("%lld %lld", &N, &M);
	long long right = 0;
	for (int i = 0; i < N; i++) {
		scanf("%lld", time + i);
		right = right > time[i] ? right : time[i];
	}
	right *= M;
	printf("%lld\n", binarysearch(1, right));
 
	return 0;
}

주의

1. 이분탐색 범위 : 조건의 최대값인 $10^{18}$ 을 무턱대고 하면 안된다.

2. 오버플로우 : int인지 unsigned int 인지 long long인지 unsigned long long 인지 확인한다.

3. 같은수가 여러번 나오면 : upper bound, lower bound

세그먼트트리는 완전탐색을 모델링하고 나면 무엇을 세그먼트트리로 구현할지 쉽게 생각할 수 있다.

요약

before < now 면서 A[before] > A[now]인

(before,now)의 쌍의 개수를 구한다.

현재 now 일 때(고정) 이전에 사용했던 before들 중에서(탐색)

A[now]보다 큰 A[before] 의 개수를 세는 것이다.

세그먼트트리 구성

- 세그먼트트리 : A가 가진 값들의 사용횟수를 저장

- 쿼리 : N > A[i] > A[j] 을 만족하는 A[i]의 개수

- 쿼리구간 : [A[j]+1, N]

개념

역으로 된 쌍을 세는 문제유형

무엇이 역으로 되어있을까?

i < j 면서 A[i] > A[j] 인 ---inversion

(i,j) 의 쌍의 개수를 구한다. ---counting

5,1,3,1,2 라는 수열이 주어졌을 때 inversion 된 쌍의 수는

(5,1)  = 1 < 2 면서 A[1]>A[2]( = 5>1)

(5,3)  = 1 < 3 면서 A[1]>A[3]( = 5>3)

(5,1)  = 1 < 4 면서 A[1]>A[4]( = 5>1)

(5,2)  = 1 < 5 면서 A[1]>A[5]( = 5>2)

(3,1)  = 3 < 4 면서 A[3]>A[4]( = 3>1)

(3,2)  = 3 < 5 면서 A[3]>A[5]( = 3>2)

이다.

즉 내림차순과 같이 순서는 뒤면서 값은 앞에 나온 수보다 작은 경우인 것이다.

i < j 면서 A[i] > A[j]인

(i,j) 의 쌍의 개수를 구한다.

를 좀 더 뜯어먹기 좋은 표현으로 바꾸면

before < now 면서 A[before] > A[now]인

(before,now)의 쌍의 개수를 구한다.

즉,

현재 now 일 때(고정) 이전에 사용했던 before들 중에서(탐색)

A[now]보다 큰 A[before] 의 개수를 세는 것이다.

구현

그러면 어떻게 i<j 면서 A[i]>A[j]인 i의 개수를 찾을 수 있을까?

시간복잡도를 계산해보자

1~N까지의 j를 기준으로 할 때 조건에 맞는 i를 찾아 쌍을 만드는 것이므로

j의 N회 순회는 반드시 필요하다.

1. $O(N \times ???)$ 

1. $O(N\times N)$ 

* [ 는 이상, ) 는 이하를 의미

$N$ : j의 순회[0, N)

$N$ : i의 순회[0, j) 완전탐색

int A[Max];
int cnt = 0;
for (int j = 0; j < N; j++)
	for (int i = 0; i < j; i++)
		if (A[i] > A[j])
			cnt++;

2. $O(N\times logN)$ 

$N$ : j 의 순회[0, N)

$logN$ : i의 순회[0, j) 세그먼트트리

int A[Max];
int cnt = 0;
for (int j = 0; j < N; j++)
	query(A[j] + 1, N);

구현_세그먼트트리

2. $O(N\times logN)$ 

$N$ : j 의 순회[0, N)

$logN$ : i의 순회[0, j) 세그먼트트리

세그먼트트리를 이용하기 위해서는

i < j

A[i] > A[j]

를 다시봐야한다.

i의 범위 : [0,j)

그래서 세그먼트트리를 구성할 때

당연히 세그먼트트리 idx = 저장된 데이터의 idx = 입력순서

로 생각할 수 있는데 세그먼트트리의 idx가 저장순서로 사용되면 의미가 없다.

요약 : 세그먼트트리 구성

- 세그먼트트리 : A가 가진 값들의 사용횟수를 저장

- 쿼리 : N > A[i] > A[j] 을 만족하는 A[i]의 개수

- 쿼리구간 : [A[j],N]

세그먼트트리로 구해야할 사항은

[0,j) 에서 A[i] >A[j]인 i의 개수

가 된다.

이때

i<j 는 [0,j) 의 범위지정으로 자연스레 조건만족이된다.

A[i] > A[j] 는 어떻게하면될까? 

자연스레 세그먼트트리의 idx를 A[i]와 A[j]의 값으로 쓸 수 있게 하는 것이다.

즉,

세그먼트트리

현재 j일 때

idx : A 값

segTree[idx] : j가 훝어온 A[j]값의 사용횟수

로 구성하는 것이다.

이 때 query의 범위는 [j+1,N) 가 되어

A[i](=이전의 j의 A[j] 값) 값이

현재 j의 A[j]값보다 큰게 몇개가 있는지 logN으로 합을 구하는 것이다.

다음과 같이 같은 값이라도 A[2]=1,A[4]=1이 구분되듯 다르게 센다.

예제

www.acmicpc.net/problem/5419-세그먼트트리(inversion counting)+좌표압축+스위핑

개념

좌표자체를 배열의 idx로 활용하는 경우가 많다.

하지만 불가능한 경우가 있다.

- 음수좌표 --> 범위가 너무 넓음에 포함됨

- 범위가 너무 넓음

결국 좌표의 범위가 너무 넓어 배열에 다 담을 수 없을 때

주어진 좌표만을 사용하도록 하기 위한 방법이 좌표 압축이다.

좌표압축 알고리즘

1. 좌표 저장 - 입력순서(idx), 좌표(pos)

2. 좌표 정렬 - 좌표(pos) 기준, 좌표같을 땐 입력(idx) 기준

3. 좌표 압축

코드

void compression() {
	int before = arr[0].pos;
	int cnt = 0;
	answer[arr[0].idx] = 0;
 
	for (int i = 0; i < N; i++) {
		if (before != arr[i].pos) {
			before = arr[i].pos;
			cnt++;
		}
		answer[arr[i].idx] = cnt;
	}
}
int main() {
	scanf("%d", &N);
 
	//1. 좌표 저장(idx,pos)
	for (int i = 0; i < N; i++) {
		scanf("%d", &arr[i].pos);
		arr[i].idx = i;
	}
	
	//2. 좌표 정렬
	mSort(0, N - 1);
	
	//3. 좌표 압축
	compression();
 
	for (int i = 0; i < N; i++)
		printf("%d ", answer[i]);
	return 0;
}

예제

www.acmicpc.net/problem/18870